Quicksort - Problem

wxSkip

Auf meinem PC fährt irgendwo noch ein iterativer Quicksort rum, der ist aber nur halb so schnell wie der Rekursive. Ich kann mich hustbaer nur anschließen:
Frag deinen Lehrer, was das Ganze soll, und mach es so elegant wie möglich:
1. Wenn du darfst, mach was anderes
2. Wenn du das machen musst, führe Funktionen ein
3. Wenn du das trotzdem nicht machen darfst, mach es iterativ und melde dich auf jeden Fall nochmal.

Wow. Was 'ne blöde Aufgabe. Quicksort ohne Rekursion. Mein Beileid!

Graffiti

Schwuppa dupps. Ich habs raus.
Es ist ja eigentlich ganz simpel.

Ich hab mich dazu entschieden, dass ich die Funktionen einführe.

Code poste ich nicht, wenn ihn jmd. will PN.

wxSkip

Graffiti schrieb:

Schwuppa dupps. Ich habs raus.
Es ist ja eigentlich ganz simpel.

Ich hab mich dazu entschieden, dass ich die Funktionen einführe.

Code poste ich nicht, wenn ihn jmd. will PN.

Gute Entscheidung . Ich würde das aber trotzdem nochmal absprechen.

P.S.: Quicksort-Code gibt es bestimmt genug im Internet, aber ich hab selber welchen

hustbaer

Ich hab' keinen.
Aber ich hab std::sort, der ist eh viel besser

wxSkip

hustbaer schrieb:

Ich hab' keinen.
Aber ich hab std::sort, der ist eh viel besser

Bei mir nur etwa 5-10% (zumindest mit Zahlen)...

Bei mir nur etwa 5-10% (zumindest mit Zahlen)...

Warum "nur"? Das ist doch schon ziemlich viel, wenn man es mal auf sortierlastige Anwendungen bezieht.

wxSkip

Irgendwer schrieb:

Bei mir nur etwa 5-10% (zumindest mit Zahlen)...

Warum "nur"? Das ist doch schon ziemlich viel, wenn man es mal auf sortierlastige Anwendungen bezieht.

Wenn du meinst...

hustbaer

std::sort ist Introsort, und damit genau gleich schnell wie Quicksort, so lange Quicksort nicht entartet. "Besser" also einfach deswegen, weil Introsort garantiert O(N log N) ist, und nicht wie Quicksort zu O(N^2) entarten kann.

Unterschiede in der Geschwindigkeit deuten daher in den meisten Fällen eher auf eine unterschiedlich gute Implementierung des Quicksort-Teils hin.

General-Purpose Sortieralgorithmus der schneller als Quicksort wäre ist mir keiner bekannt.

SeppJ

hustbaer schrieb:

std::sort ist Introsort, und damit genau gleich schnell wie Quicksort, so lange Quicksort nicht entartet.

Gleich Komplexitätsklasse != Genau gleich schnell

314159265358979

Was spricht eigentlich gegen Mergesort?

ipsec

Bei Boost ist grade eine Bibliothek namens "Sorting" auf dem Review-Scheduler, die einen Sortieralgorithmus bietet, der laut Beschreibung schneller als std::sort sei. Ich glaube das war Radixsort oder eine Variante davon.

mazal

314159265358979 schrieb:

Was spricht eigentlich gegen Mergesort?

Speicher und Zeit?

hustbaer

SeppJ schrieb:

hustbaer schrieb:

std::sort ist Introsort, und damit genau gleich schnell wie Quicksort, so lange Quicksort nicht entartet.

Gleich Komplexitätsklasse != Genau gleich schnell

Nein. Gleicher Algorithmus == Genau gleich schnell.
Nicht verstanden haben, aber gleich mal die Warnschilder auspacken.

Wikipedia schrieb:

Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted.

D.h. so lange Introsort nicht umschaltet *ist* es ein Quicksort. Der minimale Overhead die Rekursionstiefe mitzuzählen fällt dabei wirklich nicht ins Gewicht.

Jetzt klar?

wxSkip

hustbaer schrieb:

SeppJ schrieb:

hustbaer schrieb:

std::sort ist Introsort, und damit genau gleich schnell wie Quicksort, so lange Quicksort nicht entartet.

Gleich Komplexitätsklasse != Genau gleich schnell

Nein. Gleicher Algorithmus == Genau gleich schnell.
Nicht verstanden haben, aber gleich mal die Warnschilder auspacken.

Ich glaube aber (hab ich mal ausprobiert), bei kleinen Mengen (und die kommen ja bei Quicksort mit der Aufteilung bei der Rekursion vor) können andere Algorithmen durchaus schneller sein (bei mir hat das mit Heapsort funktioniert, war leicht schneller, aber immer noch langsamer als std::sort()).

EDIT:

hustbaer schrieb:

Wikipedia schrieb:

Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted.

D.h. so lange Introsort nicht umschaltet *ist* es ein Quicksort. Der minimale Overhead die Rekursionstiefe mitzuzählen fällt dabei wirklich nicht ins Gewicht.

Jetzt klar?

Hey, genau so habe ich das auch "erfunden", inklusive logarithmischer Berechnung . Und dort liegt eben auch der Unterschied in der Geschwindigkeit von Introsort.

hustbaer

ipsec schrieb:

Bei Boost ist grade eine Bibliothek namens "Sorting" auf dem Review-Scheduler, die einen Sortieralgorithmus bietet, der laut Beschreibung schneller als std::sort sei. Ich glaube das war Radixsort oder eine Variante davon.

Naja, es gibt viele Sortieralgorithmen die schneller als Quicksort sind, bloss keine mir bekannten general purpose Sortieralgorithmen.
Radixsort ist kein general purpose Sortieralgorithmus.

hustbaer

wxSkip schrieb:

EDIT:

hustbaer schrieb:

Wikipedia schrieb:

Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted.

D.h. so lange Introsort nicht umschaltet *ist* es ein Quicksort. Der minimale Overhead die Rekursionstiefe mitzuzählen fällt dabei wirklich nicht ins Gewicht.

Jetzt klar?

Hey, genau so habe ich das auch "erfunden", inklusive logarithmischer Berechnung . Und dort liegt eben auch der Unterschied in der Geschwindigkeit von Introsort.

Bist du sicher?
Bei den allermeisten Inputs schaltet std::sort nämlich nicht um.

Könnte auch daran liegen wie du das Pivot Element ermittelt hast (üblich ist "Median of 3 Medians of 3"), bzw. wann du für kleine Mengen auf Insertion-Sort umgeschaltet hast.

mazal schrieb:

314159265358979 schrieb:

Was spricht eigentlich gegen Mergesort?

Speicher und Zeit?

nee, MergeSort ist im WorstCase so schnell wie QuickSort im BestCase ...
eigentlich gibt's für MergeSort gar keinen WorstCase ...
von daher ist MergeSort zumindest theoretisch am schnellsten ...
allerdings ist es nicht so einfach, MergeSort genauso maschinenfreundlich zu
implementieren, wie QuickSort, von daher macht QuickSort wieder einiges gut ...
aber wehe, QuickSort erwischt als Pivot-Element mal etwas zu oft einen Wert,
der weit weg vom Durchschnittswert liegt! dann ist sogar bubble sort besser als
QuickSort
es gibt ein paar Studien, die wollen bewiesen haben, dass für häufiges
Sortieren 'mittelgroßer' Datenmengen (~100.000 Zahlen)
Shell-Sort noch schneller als Quick- oder sogar MergeSort sein soll ...
in einigen Sonderfällen ist allerdings auch nichts schneller als Radix-Sort,
aber leider nicht immer anwendbar
heap sort ist eine langsamere MergeSort Variante, die dafür weniger zusätzlichen
Speicher benötigt als MergeSort
Insgesamt stellt sich die Lage also circa so dar (vom schnellsten zum
langsamsten)

1. Radix Sort, Bucket Sort & Konsorten
2. MergeSort / ShellSort
3. HeapSort
4. QuickSort
4. Insertion / Selection Sort
5. Bubble Sort

Einzig MergeSort ist für jeden Fall anwendbar und kann zudem stabil
und sogar in-place (extrem komplex) implementiert werden, und wäre somit
von den vergleichsbasierten Algos der geeignetste Multi-Purpose-Algo.

Viel schneller als eine riesige Datenmenge mit z.B. 100.000.000 Einträgen
'auf einmal' zu sortieren wäre eine Umverteilung auf einzelne, kleinere
Buckets, die man dann jeweils separat mit MergeSort (falls stabil gewünscht
ist) oder ShellSort (wenn's instabil sein darf) vorsortiert, und die dann
letzten Endes wieder mit Merge() zusammenführt.

HeapSort ist nicht stabil und etwas weniger maschinenfreundlich als MergeSort,
dafür kann kein pathologischer WorstCase eintreten wie bei QuickSort.

Gegen Quicksort spricht hauptsächlich dessen Unzuverlässigkeit plus ein
Worst Case, der das Potential hat, im RL gewaltige Schäden anzurichten.
Ansonsten natürlich im Durchschnittsfall zirka ebenso schnell wie
MergeSort, aber leider auch nicht stabil.

Selection Sort, Insertion Sort oder Bubble Sort könnte man auch schon sehr
früh im Schulunterricht durchnehmen, sind hauptsächlich von pädagogischem
Nutzen, überraschen aber in einigen Spezialfällen mit dem Bestcase bei
Feldern, die schon größtenteils vorsortiert vorliegen. In solchen Fällen
sogar schneller als MergeSort und en-par mit Radix-/Bucket Sort.

So, also das alles noch mal zur Auffrischung des Uni-Lehrstoffs, den einige
schon vergessen haben. In der Praxis interessiert es nicht weiter, da nimmt
man ohnehin den Sortierer aus der Bibliothek (je nach Compiler-System ist
der Algorithmus hinter der Schnittstelle von Anbieter zu Anbieter verschieden,
auch wenn sie jedes Mal qsort oder std::sort() heißt, handelt es sich dabei
eher selten um QuickSort (wohl eher eine getunete MergeSort Variante - idR))

...

314159265358979

Einen großen Vorteil von Mergesort hast du allerdings vergessen, er lässt sich auch mit ForwardAccess implementieren und ist somit auch für Listen geeignet und gerade dort besonders effizient, weil kein zusätzlicher Speicher benötigt wird, ein splicen reicht

hustbaer

SortierFachmann schrieb:

(komisches Getrolle)

Dass Merge-Sort im average case schneller (oder auch nur gleich schnell) sein soll als Quicksort ist purer Unfug.
Dass Quicksort dafür worst case schlecht aussieht ist unbestritten.
Deswegen verwendet man ihn ja auch nicht alleine.