Welcher Sortieralgorithmus ist unter welchen Umständen der schnellste?

Nabend.

Da ich mich ja mit der Programmierung beschäftige, habe ich versucht, einige Sortieralgorithmen in C++ nachzuprogrammieren (und mir danach die schnelleren Versionen aus dem Netz raus zu suchen). Dann wollte ich anhand einer Liste von 500.000 Elementen testen, welcher Algorithmus der Schnellste ist.

Getestet habe ich bisher std::sort, Quick Sort, Insertion Sort und Timsort. std::sort war bei der unsortierten Liste zwei Millisekunden schneller als Timsort, danach folgte Insertion Sort und Quick Sort war letzter. Wenn ich aber ein neues Element zu der sortierten Liste hinzugefügt habe, war Timsort der schnellste Algorithmus mit sage und schreibe 0 Mikrosekunden. Danach folgten Insertion Sort, std::sort und zu guter letzt war mal wieder Quick Sort fertig.

Wenn ich das ganze kurz zusammenfassen sollte, würde ich sagen, dass Timsort an dieser Stelle der beste Sortieralgorithmus ist, auch wenn er zwei Millisekunden langsamer bei der Sortierung einer komplett unsortierten Liste als std::sort ist. Zwei Millisekunden sind vernachlässigbar, vor allem, wenn std::sort bei der Sortierung der bereits sortierten Liste mit einem neuen Element 9 Millisekunden braucht, während Timsort nicht mal eine Mikrosekunde benötigt.

Gibt es Sortieralgorithmen, die noch schneller sind als die vier vorhin genannten? Oder welche anderen Szenarien könnte ich testen?

Gruß

Answer 1

[regex9]

Wenn der Timsort beim zweiten Durchlauf schneller war (vor allem mit einer Laufzeit von 0ms), dann muss das Sortierergebnis vom ersten Durchlauf gecached worden sein.

Bezüglich der std::sort-Funktion kann ich mir gut vorstellen, dass bei der Implementierung alle Möglichkeiten ausgenutzt wurden, die C++/der Compiler anbieten, um die Performance zu verbessern. Man wird sicherlich mit Pointern und Templates gearbeitet haben und einer Kombination verschiedener Sortieralgorithmen.

Was du noch untersuchen könntest:

• Listen statt Arrays
• ein Aggregat mit jeweils 10, 100 und 1.000.000 Elementen
• ein Aggregat mit einer ungeraden Anzahl an Elementen

Bezüglich schnellerer Sortierverfahren: Sortieralgorithmen sind von ihrem Einsatzgebiet abhängig. Ein Quicksort wird nicht seine volle Stärke ausspielen können, wenn er nur eine kleine Menge an Elementen sortieren soll oder sein Pivot-Element schlecht gewählt wird.

Orientieren würde ich mich wohl an der O-Notation (im average case). Für weitere Sortierverfahren kannst du hier schauen: https://de.wikipedia.org/wiki/Sortierverfahren

Außerdem kannst du, wie hier in anderen Antworten schon angemerkt, sicherlich noch an der Implementierung feilen. Achte darauf, was du für Vergleichsfunktionen verwendest, was für Datentypen, etc..

Answer 2

[W00dp3ckr]

Deine Frage entspricht nicht dem, was Du testest. Du vergleichst eigentlich Implementierungen auf einer gegebenen Architektur mit einem gewissen Compiler.
Wie auch mein Vorredner sagt, ist nur ein kleiner Teil der eigentliche Sortieralgorithmus, die Implementierung spielt eine große Rolle. Sind die Vergleichsalgorithmen überall gleich?

Was für ein Sortierverfahren nutzt eigentlich Dein std::sort ?

Answer 3

[adenosi]

Ich würde mir an deiner Stelle die Algorithmen der Sortierungen ansehen und diese dann selber nachzuprogrammieren.

Ebenfalls kann es sein das sich manche Algorithmen für bestimmte Fälle besonders gut eignen.

Answer 4

[TeeTier]

Die Antwort ist ganz einfach: Es gibt keinen "schnellsten" Sortieralgorithmus.

Denn es hängt extrem vom Anwendungsfall ab:

1. Soll / muss / darf das Ergebnis stabil sein? (z. B. wenn du mehrfach hintereinander nach unterschiedlichen Kritieren sortieren möchtest)
   
2. Ist dir Geschwindigkeit oder Speicherverbrauch wichtiger? (Wird einmalig bei der Initialisierung eines Embedded-Computers sortiert, oder dauerhaft im Betrieb eines starken Desktops?)
3. Sind die vorliegenden Daten schon zu großen Teilen vorsortiert?
4. Sind die Daten evtl. oftmals schon sortiert, allerdings rückwärts?
5. Sind die Daten wirklich zufällig verteilt?
6. Werden Container von Zeigern, Referenzen oder ganzen Objekten sortiert?
7. Welche Art von Container liegt vor?
8. Hast du wahlfreien Zugriff auf die Elemente, oder kannst du dich nur "durchhangeln"?
9. Darf das Ergebnis vielleicht sogar Fehler enthalten, d. h. falsch sortierte Einträge enthalten? (Lach nicht, dafür gibt es tatsächlich Anwendungsfälle!)
   

Es gibt noch eine Million weitere Punkte, die zu berücksichtigen sind, und wie du siehst, kann es aufgrund der verschiedenen Anforderungen keinen besten Algorithmus geben. :)

Im Übrigen ist korrektes Profiling eine Kunst. Dabei gibt es unglaublich viele Dinge, die du nicht beachtest, und die dir dann falsche Ergebnisse liefern, die du vermeintlich für richtig hältst. Deine genannten Zahlenwerte machen einen solchen Eindruck!

Du solltest unbedingt die Last so erhöhen, dass du mindestens im zweistelligen Sekundenbereich bist, denn bei 9ms ist einfach viel zu viel Spielraum für "Dreckeffekte", die jede Aussage zu Nichte machen. :)

Naja, viel Spaß noch! Aber ohne vernünftige Vorgaben kann man nicht sagen, was das "Beste" ist. :)

PS: TimSort ist ja der Standard-Sortier-Algorithmus in Java und hatte vor ca. einem Jahr noch einen Bug, sodass u. U. einige Listen von Eingangsdaten fehlerhaft sortiert wurden. Das Lustige daran ist, dass es ewig keiner gemerkt hat und dann plötzlich alle: "Java sortiert falsch! Aaahhh!". :)

Such mal bei Google nach "java timsort bug" ... interessante Geschichte! ;)

Answer 5

[DerCo]

wenn nach dem hinzufügen eines Elements 0ms reichen, würde ich sagen, du hast den Kram im Cache - hast du den heap dealloziert nach der Routine? Sonst stimmen deine Ergebnisse alle nicht.

Was sortierst du eigentlich? Ein simples Array mit Randomdaten?

Was ist mit bubble sort? Schon probiert?

Comments

[PeterLustig1999]

Ich habe mir mein unsortiertes Array kopiert, sortieren lassen und danach die sortierte Kopie wieder gelöscht. Gemessen habe ich nur die Zeit, die das reine sortieren gebraucht hat.

Ich sortiere ein simples Array mit Randomdaten, wie du bereits sagst. Des unsortierte Array speichere ich jedoch zwischen, sodass jeder Algorithmus quasi mit dem gleichen Array startet.

Weiterhin habe ich das Ganze mehrfach getestet und mich nicht nur auf ein Testergebnis beschränkt. Generell ist std::sort bei der ersten Sortierung ungefähr 2 ms schneller als Timsort, generell benötigt Timsort bei der zweiten Sortierung immer 0 mikrosekunden.

Bubble Sort habe ich noch nicht ausprobiert, könnte ich vielleicht einmal versuchen.

[DerCo]

@PeterLustig1999

naja das mit bubble war eher für die Vollständigkeit, Qsort ist, wenn ich mich richtig erinnere quasi so etwas wie der "Nachfolger"; insofern wird es sicher keine Top-Werte liefern.

Für eine spätere Anwendung wird es nicht nur entscheidend sein, wie viel Daten du hast, sondern auch wie komplex sie sind, also wie oft die schleifen laufen und wie tief die Rekursionen werden (schliesslich gibt es auch hier eine Grenze, bei der du in den "too many nested scopes"-Fehler rennst).

Für eine poplige Adresssortierung ist es schlicht irrelevant, was du nimmst, da hier ein paar Millisekunden mehr oder weniger nicht ins Gewicht fallen; Ganz anders sieht das aus, wenn du z.B. mit Suggests arbeitest (das ist das was Google macht, dass direkt bei der Eingabe der User Vorschläge ausgespuckt werden, die ja über Ajax geladen werden müssen).

Wieder etwas völlig anderes ist beispielsweise eine Programm um Daten zu ver/ent-schlüsseln.

Um es kurz zu machen; jeder Algorithmus hat seine Stärken und Schwächen und abgesehen davon, dass es eine gute Übung ist, wirst du in Zukunft deine Wahl abhängig von der Aufgabenstellung treffen müssen; da helfen dir deine jetzt ermittelten Testwerte nicht weiter.

[DerCo]

@DerCo

Bevor ich es vergesse: WO du richtig was gutmachen kannst, ist bei der klugen Auswahl der verwendeten Stringoperatoren.
Ein
strpos, ein substr oder, wenn möglich ein Byteshift, sind je nach
Stringaufbau und -länge verschieden schnell - hier lassen sich ggf.
sogar SEKUNDEN einsparen!

[regex9]

@DerCo

Ich habe mich schon gewundert. Der BubbleSort ist ein etwas langsames Sortierverfahren im Vergleich zu anderen (mit einem Laufzeitverhalten von O(n²)).

[DerCo]

Zu Teil 2 deiner Frage: Eine kluge Indizierung ist wertvoller als der coolste Algo, da du von vorneherein die betroffenen Datensätze extrem einschränken kannst; darum ist z.B. eine clevere Datenbank 1000mal mehr wert als das geilste Script.

Alleine über Restrukturierung einiger SQL-Datenbanken konnte ich die Scriptlaufzeiten bis zu 800% schneller machen; hab den alten Kram selbst verbrochen, aber man lernt ja immer wieder was neues und ab und zu lohnt das Nachschauen :)
Trotzdem wie gesagt: Indizierung ist extrem wertvoll; ich habe alle Emails seit 1997 (immerhin 20 Jahre) in meiner Datenbank; das sind knapp 300GByte -  und durchsuche nach beliebigen Kriterien in 10-15 Sekunden; nach bestimmten Indexfeldern in unter 1 Sek.