Quicksort und nicht stören?

Überlegen Sie sich beim Schreiben von Standardanwendungen (ohne HPC), welchen Sortieralgorithmus Sie auswählen sollen, oder entscheiden Sie sich einfach für Quicksort (was die meisten Bibliotheken nur als Sortieren bezeichnen)? Bis zu einem gewissen Grad kann es in bestimmten Situationen rentabel sein, andererseits erfordert eine ordnungsgemäße Optimierung einige Zeit, um das Problem zu analysieren und Benchmarks zu erstellen.

Im Allgemeinen hält die Verwendung der Standardmethoden, sofern nicht ausdrücklich etwas Exotischeres getan werden muss, IMHO alles viel besser lesbar / verständlicher.

Wenn Sie feststellen (oder in einigen Fällen stark vermuten), dass Sie ein Leistungsproblem haben, ist es an der Zeit, die Komplexität zu erhöhen.

Wenn Sie jedoch eine Sprache verwenden, die so niedrig ist, dass es keine integrierte Sortierung für die Art von Objekten gibt, die Sie sortieren müssen, versuchen Sie, eine oder zwei auszuwählen, die alle Ihre Basen abdecken, und diese zu implementieren.

Rufen Sie immer die bereitgestellten Bibliotheksroutinen auf, es sei denn, Sie haben sehr, sehr gute Gründe, dies nicht zu tun (und Sie müssen dokumentieren, warum dies so ist).

Dies liegt daran, dass es schwierig ist, Sortieralgorithmen absolut richtig zu machen. Es gab einen Fehler im Java-Quicksort mit sehr großen Datenmengen, der von Sun identifiziert, behoben und an Kunden geliefert wurde, sodass Sie dies nicht tun mussten.

Auch die Standardsortierung in Java 7 wurde auf eine neuere, bessere Sortierung aktualisiert. Auch kostenlos.

Bleiben Sie dabei, es sei denn, die Standardsortierung ist nachweislich nicht gut genug für Sie.

Auf einer Konferenz hörte ich einmal eine schöne Geschichte darüber.

Bei Microsoft schrieb jemand eine VB-App (ca. VB 3) und schickte eine Reihe von Leuten per E-Mail, die sagten, er habe eine Menge Werte und er wollte, dass sie in der Combobox angezeigt werden, wie sollte er vorgehen?

Alle suchten nach ihren alten Lehrbüchern aus der Informatik, suchten nach hocheffizienten Routinen, portierten sie nach Visual Basic und schickten sie ihm zu. Einer hat gerade zurückgeschickt "Wie viele Werte in der Combobox?".

"Ungefähr 50" kam die Antwort.

"Setzen Sie einfach die sortierte Eigenschaft auf TRUE".

In 99,9999% der Instanzen erfolgt die Sortierung am besten mithilfe einer Bibliothek, eines Steuerelements oder in der SQL-Auswahl, da der Leistungsunterschied zwischen der Bibliotheksroutine und allem, was Sie schreiben, vernachlässigbar ist und der Aufwand und der Wartungsaufwand die Konsequenzen massiv überwiegen.

Dies ist die Zeit, um das klassische Zitat über vorzeitige Optimierung herauszuholen. In den meisten Fällen spielt es wirklich keine Rolle. Heck, mit der Geschwindigkeit von CPUs in diesen Tagen könnten Sie wahrscheinlich die meisten Datensätze blasensortieren und nicht wirklich viel bemerken. Wenn Sie jedoch wirklich große Datenmengen sortieren und die Sortierleistung zu einem Problem wird, sollten Sie auf jeden Fall andere Optionen in Betracht ziehen.

Obwohl es für die Bits und Zeitscheiben offensichtlich keine Rolle spielt. Ich finde Merge Sort einfacher zu schreiben und zu verstehen als Quicksort. Wenn ich also meinen eigenen Sortieralgorithmus schreibe, würde ich das verwenden.

Zumindest in einer kompetent geschriebenen Bibliothek würde ich erwarten, dass das integrierte System als Introsort und nicht nur als Quicksort sortimplementiert wird . Der Unterschied ist selten von großer Bedeutung, aber Introsort eliminiert die schlechte Worst-Case-Leistung von Quicksort mit minimalen Auswirkungen auf die häufigsten Fälle.

Um Ihre Frage jedoch zu beantworten: Ja - damit sollten Sie normalerweise beginnen, und bis / sofern Sie keine Profiler-Ergebnisse haben, die darauf hinweisen, dass es sich um ein Problem handelt, sollte es dort bleiben.