Es ist eine bekannte Sache mit Quicksort, dass, wenn sich der Datensatz in oder fast in der Sortierreihenfolge befindet, die Leistung fürchterlich 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, der einen Datensatz durchläuft, einen Vergleichsfaktor anwendet und einen Bericht darüber zurückgibt, 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.
Wie Sie wahrscheinlich erwarten würden, wird einiges darüber nachgedacht. Die Median-of-Three-Methode bedeutet, dass das Worst-Case-Verhalten von Quicksort nicht für sortierte Daten auftritt, sondern für weniger offensichtliche Fälle.
Introsort ist ziemlich aufregend, da es den quadratischen Worst-Case von Quicksort insgesamt vermeidet. Statt Ihrer natürlichen Frage: "Wie stelle ich fest, dass die Daten nahezu sortiert sind", fragt sie sich selbst, wie sie sich entwickelt, "dauert das zu lange?". Wenn die Antwort ja ist, wechselt es von Quicksort zu Heapsort.
Timsort kombiniert Zusammenführungssortierung mit Einfügesortierung und führt sehr gut bei sortierten oder umgekehrt sortierten Daten und Daten aus das schließt sortierte oder umgekehrt sortierte Teilmengen ein.
Wahrscheinlich lautet die Antwort auf Ihre Frage: "Sie brauchen keine Vorab-Analyse, Sie brauchen einen adaptiven Sortieralgorithmus."
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.
Lange knifflige PDF: Ссылка
Wenn Ihre Daten jedoch wirklich riesig sind und Sie seriell zugreifen müssen, ist Mergesort wahrscheinlich das Beste. Es ist immer O (N log N) und es hat ausgezeichnete "Lokalität" -Eigenschaften.
Ich habe noch keine Vorsortierungsanalyse gehört, aber ich bin der Meinung, dass Sie, wenn Sie das Dataset durchgehen, um es zu analysieren, die Leistung Ihrer gesamten Sortierzeit bereits in Anspruch nehmen.
Um vollständig zu analysieren, um zu entscheiden, welcher Algorithmus zu verwenden ist, werden Sie fast die Sortierarbeit erledigen. 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).
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 des 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 Gegenstand im zweiten Teil sehen Sie, ob der Gegenstand & lt; als das letzte Element im ersten Teil 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 speziellen Fall optimiert.
QuickSort ist nur dann ein Problem, wenn der Datensatz riesig ist und bereits größtenteils sortiert ist, würde ich die folgenden Heuristiken verwenden (bis eine vollständige Lösung vorliegt):
Bitte nicht stören, wenn die Datensatzgröße unter dem Schwellenwert liegt.
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.
Um einen konzeptuellen Punkt zu machen, den die Leute noch nicht gemacht haben: Quicksort ist ein Common-Sense-Algorithmus zum Teilen und Herrschen 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 hätte Merge Sort einfach beliebter als Quicksort. (Und vielleicht war das Hinzufügen von "schnell" zum Namen eine gute Verkaufskunst.)