Analysealgorithmus vorsortieren?

Question

Es ist eine bekannte Sache mit Quicksort, dass, wenn der Datensatz in oder fast in der Sortierreihenfolge ist, die Leistung auf schreckliche Weise abnimmt. In diesem Fall ist die normalerweise sehr langsame Einfügesortierung die beste Wahl. Die Frage ist zu wissen, wann was zu verwenden ist.

Gibt es einen Algorithmus zum Durchlaufen eines Datensatzes, zum Anwenden eines Vergleichsfaktors und zum Zurückgeben eines Berichts darüber, wie nahe der Datensatz in der Sortierreihenfolge sein soll? Ich bevorzuge Delphi/Pascal, aber ich kann andere Sprachen lesen, wenn das Beispiel nicht übermäßig komplex ist.

Answer 1

Wie Sie erwarten würden, ist ziemlich viel darüber nachzudenken. Die Median-of-Three-Methode bedeutet, dass das Worst-Case-Verhalten von Quicksort für sortierte Daten nicht auftritt, sondern für weniger offensichtliche Fälle.

Introsort ist ziemlich aufregend, da es Quicksorts quadratischen Worst-Case insgesamt vermeidet. Statt Ihrer natürlichen Frage: "Wie stelle ich fest, dass die Daten fast sortiert sind", fragt sie sich selbst, wie sie sich entwickelt, "dauert das zu lange?". Wenn die Antwort ja lautet, wechselt sie von Quicksort zu Heapsort.

Timsort kombiniert Merge-Sort mit Insertion-Sort und führt sehr gut bei sortierten oder umgekehrt sortierten Daten und bei Daten, die sortierte oder umgekehrt sortierte Subsets enthalten.

Also wahrscheinlich die Antwort auf Ihre Frage ist, "Sie brauchen keine Pre-Pass-Analyse, Sie brauchen einen adaptiven Sortieralgorithmus".

Answer 2

Ich habe noch keine Vorsortierungsanalyse gehört, aber ich bin der Meinung, dass Sie, wenn Sie den Datensatz zur Analyse durchgehen, bereits die Leistung Ihrer gesamten Sortierzeit reduzieren.

Answer 3

Eine mögliche Lösung besteht darin, das erste, das letzte und das mittlere Element im aktuellen Sortierbereich (während der QuickSort-Operation) zu verwenden und das mittlere Element als Pivotelement auszuwählen.

Answer 4

Um vollständig zu analysieren für den Zweck der Entscheidung, welcher Algorithmus zu verwenden ist, werden Sie fast die Arbeit des Sortierens tun. Sie könnten so etwas wie die Werte zu einem kleinen Prozentsatz zufälliger, aber zunehmender Indizes überprüfen (dh eine kleine Stichprobe der Elemente analysieren).

Answer 5

Es gibt auch SmoothSort, das anscheinend ziemlich schwierig zu implementieren ist, aber es variiert zwischen O (N log N) und O (N), je nachdem, wie sortiert die Daten beginnen sollen.

http://en.wikipedia.org/wiki/Smoothsort

Lange heikel PDF: http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

Allerdings, wenn Ihre Daten wirklich sehr groß ist, und Sie müssen es seriell zuzugreifen, ist mergesort wahrscheinlich das beste. Es ist immer O (N log N) und es hat ausgezeichnete "Lokalität" -Eigenschaften.

Answer 6

Sie müssten immer noch alle Datensätze durchlaufen, um festzustellen, ob sie sortiert sind oder nicht. Um die Leistung zu verbessern, beginnen Sie mit dem ersten Datensatz und führen Sie den Rest durch, bis Sie entweder etwas nicht richtig sortiert bemerken oder das Ende erreichen Die Liste. Wenn Sie einen Fehler finden, dann sortieren Sie nur die Artikel von dieser Position bis zum Ende (da der Anfang der Liste bereits sortiert ist).

Bei jedem Artikel im zweiten Teil, sehen Sie, ob der Artikel < als das letzte Element im ersten Teil ist und wenn ja, verwenden Sie eine Einfügesortierung nur in den ersten Teil. Ansonsten Quicksort gegen alle anderen Gegenstände im zweiten Teil. Auf diese Weise ist die Sortierung für den jeweiligen Fall optimiert.

Answer 7

QuickSort beng ein Problem nur, wenn die Datenmenge sehr groß ist und bereits größtenteils sortiert, würde ich die folgenden Heuristiken verwenden (eine vollständige geblasen Lösung pending):

• Kümmern Sie sich nicht, wenn Datensatz Größe ist unterhalb der Schwelle.

• Wenn Sie einen schnellen (indizierten) Zugriff auf Datensätze (Elemente) haben, nehmen Sie ein Beispiel mit 1 Datensatz in jedem N-Datensatz und sehen Sie, ob sie bereits sortiert sind. Sollte für eine kleine Probe schnell genug sein und Sie können dann entscheiden, ob Sie schnell sortieren möchten oder nicht.

Answer 8

Um einen konzeptionellen Punkt zu machen, den die Leute noch nicht gemacht haben: Quicksort ist ein common-sense Divide-and-Conquer-Algorithmus mit einem offensichtlichen Fehler in seltenen Fällen. Angenommen, Sie möchten einen Stapel Studentenpapiere sortieren. (Was ich mit einiger Regelmäßigkeit tun muss.) Im Quicksort-Algorithmus wählen Sie etwas Papier, den Drehpunkt. Dann teilen Sie die anderen Papiere je nachdem, ob sie vor oder nach dem Drehpunkt sind. Wiederholen Sie das dann mit den beiden Substapeln. Was ist der Fehler? Der Pivot könnte ein Name sein, der nahe einem Ende der Liste statt in der Mitte liegt, so dass es nicht viel bringt, ihn in zwei Stapel zu teilen.

Merge sort ist ein anderer Divide-and-Conquer-Algorithmus, der in einer anderen Reihenfolge funktioniert. Sie können zwei sortierte Listen in linearer Zeit zusammenführen. Unterteilen Sie die Papiere in zwei gleiche oder fast gleiche Stapel, sortieren Sie sie dann rekursiv und fügen Sie sie dann zusammen. Merge sort hat keine Fehler. Ein Grund dafür, dass Quicksort beliebter ist als das Zusammenführen, ist historisch: Quicksort ist schnell (normalerweise) und es funktioniert ohne zusätzlichen Speicher. Heutzutage kann es jedoch wichtiger sein, Vergleiche zu speichern, als Speicher zu sparen, und die tatsächliche Umordnung wird oft durch das Permutieren von Zeigern abstrahiert. Wenn die Dinge schon immer so gewesen wären, dann würde ich vermuten, dass Merge Sort einfach populärer gewesen wäre als Quicksort. (Und das Hinzufügen von "schnell" zum Namen war eine gute Verkaufsmethode.)