Warum wird Quicksort als "an Ort und Stelle" beschrieben, wenn die Unterlisten viel Speicherplatz beanspruchen? Sicherlich ist nur so etwas wie eine Blasensorte vorhanden?

7

Quicksort wird als "an Ort und Stelle" beschrieben, verwendet jedoch eine Implementierung wie:

def sort(array):
    less = []
    equal = []
    greater = []
    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return sort(less) + equal + sort(greater)
    else:
        return array

Sie müssen für jede Rekursion eine Kopie der Liste erstellen. Bei der ersten Rückkehr haben wir im Gedächtnis:

  • Array
  • größer + gleich + kleiner

Dann haben wir durch die zweite Rekursion über alle Unterlisten:

  • Array
  • größer, gleich, kleiner von der ersten Rekursion
  • größer + gleich + kleiner von kleiner1, größer + gleich + kleiner von größer1

usw...

Ist das nur schlecht geschriebener Code oder habe ich Recht, wenn ich denke, dass Sie für eine große Liste tatsächlich proportional genügend zusätzlichen Speicherplatz benötigen, um diesen zu speichern?

Wenn ich an etwas denke, das "an Ort und Stelle" ist, denke ich an die Blasensortierung, bei der einfach Elemente in der Liste ausgetauscht werden, z. B .: Http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px. gif

BubbleSort benötigt nur 1 zusätzliche Variable, um ein potenziell vertauschtes Element zu speichern.

LittleBobbyTables
quelle
1
Ich kann nicht sagen, was Sie fragen. Möchten Sie versuchen, die Frage zu bearbeiten, um Ihre Frage klarer zu machen? Fragen Sie nur, ob es möglich ist, QuickSort direkt zu implementieren? Wenn ja, ist dies eine Standardfrage mit einer Standardantwort an den üblichen Stellen - Sie haben nicht genug recherchiert. PS Sie könnten auch versuchen, Ihre Formulierung präziser zu gestalten. Zum Beispiel kann ich nicht sagen, was der erste Satz sagt (es scheint ein Verb zu fehlen). Im zweiten Satz kann ich nicht sagen, wer das "Du" ist.
DW
1
In-Place bedeutet, dass Sie die Verwendung externer Datenbereiche vermeiden können, aber nur das ursprüngliche Array verwenden, das Sie sortieren. Diese Implementierung macht das nicht.
Thorbjørn Ravn Andersen

Antworten:

21

Diese spezielle Implementierung von Quicksort ist nicht vorhanden. Die Datenstruktur wird als Liste behandelt, die nur in eine Richtung wachsen kann (in diesem Fall wäre eine Zusammenführungssortierung einfacher und schneller). Es ist jedoch möglich, eine direkte Implementierung von Quicksort zu schreiben, und dies wird normalerweise so dargestellt.

In einer In-Place-Implementierung wird die Sortierfunktion stattdessen nicht rekursiv für neu erstellte Arrays aufgerufen, die immer kleiner werden, sondern für Grenzen, die immer näher kommen.

def sort(array, start, end):
    if end >= start: return
    pivot = array[start]
    middle = start + 1
    for i in range(start+1, end):
        if array[i] >= array[middle]:
            tmp = array[i]
            array[i] = array[middle]
            array[middle] = tmp
            middle += 1
    sort(array, start, middle)
    sort(array, middle, end)

(Hüten Sie sich vor diesem Code, ich habe ihn nur eingegeben, nicht bewiesen. Alle Fehler, die Sie einzeln beheben können, können Sie beheben. Bei Implementierungen in der Praxis wird für kleine Größen ein anderer Algorithmus verwendet, der jedoch kein Einfluss auf das asymptotische Verhalten hat -world-Implementierungen würden einen besseren Pivot wählen, aber darauf werde ich hier nicht eingehen , da dies für diese Frage nicht wirklich der Fall ist.)

Die Wikipedia-Seite enthält sowohl eine nicht vorhandene als auch eine direkte Version des Algorithmus.

Quicksort wie hier geschrieben erfordert O(d)+s zusätzlicher Speicher, wo d ist die Tiefe der Rekursion (die von der Pivot-Qualität abhängt) und sist die Elementgröße. Die Stapelgrößenanforderung kann verbessert werden: Es gibt zwei rekursive Aufrufe, und wir können den zweiten zu einem Endaufruf machen (der keinen Stapel verbraucht). Wenn wir immer zuerst den rekursiven Aufruf für die kleinere Hälfte ausführen, dann die maximale Stapelgröße für Array-Längen bis zun befriedigt S^(n)S^(m) mit mn/2S^(n/2), damit S^(n)lg2(n)S^(1). So können wir erreichenO(logn)+s zusätzlicher Speicherbedarf, unabhängig von der Wahl des Drehpunkts.

Es gibt viele andere Sortieralgorithmen, die direkt implementiert werden können, einschließlich Einfügesortierung, Auswahlsortierung und Heap-Sortierung. Die einfache Form der Zusammenführungssortierung ist nicht vorhanden, es gibt jedoch eine komplexere Variante .

Vielen Dank an Aryabhata für den Hinweis, dass Quicksort immer in ausgeführt werden kannlg(n) Stapel und dass es eine Variante der Zusammenführungssortierung mit beiden gibt O(1) zusätzlicher Speicher und O(nlog(n)) Laufzeit.

Gilles 'SO - hör auf böse zu sein'
quelle
1
@ Gilles: Nein. Auch wenn der Pivot-Auswahlalgorithmus immer das Minimum gewählt hat, können wir Quicksort zur Verwendung implementieren O(logn)Platz. (Sie könnten jedoch argumentieren, dass dies eine Variante von Quicksort ist). Der Schlüssel ist, immer auf der kürzeren Partition und auf der längeren Partition zu rekursieren.
Aryabhata
1
Übrigens denke ich, dass die Fusion vor Ort mit O(nlogn)wurde auch erreicht. akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/04/… beansprucht eine lineare zeitliche Zusammenführung.
Aryabhata
3

Zusätzlich zu Gilles 'Antwort können Sie Quicksort auch mit Ihrem Code einrichten, wenn Sie verknüpfte Listen anstelle von Arrays verwenden. Stellen Sie einfach sicher, dass Sie das Element aus der ursprünglichen Liste entfernen, wenn Sie es an eine der kleineren Listen anhängen.

Der folgende Pseudocode setzt / garantiert:

  • Der erste Eintrag in jeder Liste (im Folgenden als Kopf bezeichnet) starrt kein Element an und ermöglicht es, Zeiger auf die Liste bei Änderungen intakt zu halten. new listErstellt eine Liste bestehend aus einem Kopf mit dem NILnächsten Zeiger.
  • sortNimmt einen Zeiger auf einen Kopf und gibt einen Zeiger auf das letzte Element der sortierten Liste zurück. Der als Argument angegebene Zeiger ist auch der Kopf der sortierten Liste.
  • Der Speicherort jedes Elements und des Listenkopfs bleibt gleich.

.

sort(list):
    less_cur = less = new list
    equal_cur = equal = new list
    greater_cur = greater = new list
    if list.next != NIL:
        cur = list.next
        pivot = cur.value
        while cur != NIL:
            list.next = cur.next
            if cur.value < pivot:
                less_cur.next = cur
                less_cur = less_cur.next
            if cur.value == pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            if cur.value > pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            cur = cur.next
        less_cur.next = greater_cur.next = NIL
        less_last = sort(less) 
        list.next = less.next
        less_last.next = equal
        greater_last = sort(greater)
        equal_cur.next = greater.next
        return greater_last
    else:
        return list

Obwohl aus dem obigen Code eine gewisse Optimierung möglich ist, hat diese Implementierung einen größeren Speicheraufwand als die Array-basierte Implementierung in Gilles 'Antwort. Darüber hinaus leidet es in der Praxis unter dem Problem, dass verknüpfte Listen normalerweise weniger lokalisiert sind und daher eine größere Anzahl von Cache-Fehlern verursachen als das Verwalten derselben Daten in einem Array.

Diese Implementierung ist jedoch von Vorteil, wenn Sie durch Sortieren Zeiger auf die Elemente pflegen müssen. Es ist auch gut, sich dessen bewusst zu sein, wenn Sie Ihre Daten aus Gründen, die nicht mit dem Sortieren zusammenhängen, in einer verknüpften Liste speichern. (Wenn die richtige Sortierung von Bedeutung ist, kommt eine Konvertierung zwischen Liste und Array wahrscheinlich nicht in Frage.)

FrankW
quelle
Dies betrachtet "an Ort und Stelle" als "die Elemente nicht kopieren müssen", macht aber wiederum viel Arbeit mit allen Listen, die auf die Elemente verweisen. Ich würde die Verwendung all dieser zusätzlichen Datenstrukturen (die alle als Müll enden, der gesammelt werden muss) als nicht vollständig "an Ort und Stelle" betrachten
Thorbjørn Ravn Andersen
@ Thorbjørn Sie können das Entfernen aus der ursprünglichen Liste und das Anhängen an die kleinere Liste durchführen, indem Sie 2 Zeiger ändern (4 für doppelt verknüpfte Listen). Ich sehe nicht, wo dies Müll erzeugt.
FrankW
Vielleicht sollten Sie eine Implementierung Ihrer Vorschläge zeigen, um sicherzustellen, dass wir dasselbe diskutieren.
Thorbjørn Ravn Andersen
@ ThorbjørnRavnAndersen Einer in Common Lisp ist der Schafstrick von The Pitmanual . Es ist nicht "an Ort und Stelle", da der Listenknoten, der der ursprüngliche Anfang der Liste war, möglicherweise nicht später vorhanden ist, aber keinen zusätzlichen Speicher benötigt. Durch die Partitionierung wird die Listenstruktur destruktiv geändert, sodass die Unterlisten aus denselben Listenknoten wie die ursprüngliche Liste erstellt werden. Dies erfordert natürlich die Möglichkeit, die Struktur der Liste zu ändern, was einige Implementierungen (z. B. die List-Schnittstelle von Java) nicht bieten.
Joshua Taylor
@FrankW Ich denke nicht, dass es richtig ist, dies "an Ort und Stelle" zu nennen, sondern "ohne zusätzlichen Speicher". Ein Listenknoten an Position i vor dem Sortieren der Liste befindet sich möglicherweise nicht an Position i danach.
Joshua Taylor