h1

Sortieralgorithmik in Python – Teil3 Mergesort

November 1, 2008

Heute wenden, wir uns Mergesort zu, ein stabiler rekursiver Algorithmus der nach dem „Teile und Herrsche“ – Prinzip vorgeht!

Prinzip:
Bei Mergesort wird die unsortierte Liste in immer kleiner werdende Teile aufgeteilt, die dann jede einzeln für sich sortiert werden. Anschließend werden die einzelnen Stücke dann im Reißverschlussverfahren wieder zusammgeführt, bis die Liste wieder vollständig und sortiert ist!

Hier wieder mal ein Bild zum besseren Verständnis:

Mergesort - Funktionsweise

Mergesort - Funktionsweise

und hier das ganze nochmal an einem Beispiel:

Mergesort - Beispiel

Mergesort - Beispiel

die Implentierung in Python sieht folgendermaßen aus:

# MergeSort in Pyhton
import random
import time

def mergesort(seq):
    if len(seq) <= 1:
        return seq
    else:
        linkeListe = seq[:len(seq)/2]
        rechteListe = seq[len(seq)/2:]
        return merge(mergesort(linkeListe), mergesort(rechteListe))

def merge(linkeListe, rechteListe):
    newList = []
    while linkeListe != [] and rechteListe != []:
        if linkeListe[0] <= rechteListe[0]:
            newList.append(linkeListe[0])
            del linkeListe[0]
        else:
            newList.append(rechteListe[0])
            del rechteListe[0]

    while linkeListe != []:
        newList.append(linkeListe[0])
        del linkeListe[0]

    while rechteListe != []:
        newList.append(rechteListe[0])
        del rechteListe[0]

    return newList

list = []
for rand in range(10000):
    rand = random.randint(1,10000)
    list.append(rand)

ausgabe = mergesort(list)
print ausgabe

Und zu guter letzt wie immer das Benchmark:

10.000 Datensätze : 0.21s
100.000 Datensätze : 7.1s
1.000.000 Datensätze : über 15 Minuten -> nicht geeignet für Listen dieser Größe

Morgen folgt: Quicksort

One comment

  1. Der merge() lässt sich in O(n) durchführen, der hier gezeigt merge() hat jedoch eine Laufzeit von O(n^2) womit der gesamte Algoritms in quadratischer Laufzeit resultiert( del erfordert ein shiften des arrays).



Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: