DAS WETTRENNEN der Algorithmen
-
Aloah zusammen,
Wollte mal fragen welcher Sortieralgorithmus zur Zeit am schnellsten ist, wie dieser funktioniert und wie ich den in C++ implementieren...doch nicht wohl QuickSort oder (nichts gegen QuickSort...aber der ist doch schon älter oder ?! ^^)
Danke für Antworten...
MfG CodeFinder
-
Also bei Wikipedia habe ich zumindest eine Tabelle gefunden in denen die Geschwindigkeiten zu den verschiedenen Fällen verschiedener Algorithmen aufgelistet ist:
http://de.wikipedia.org/wiki/SortieralgorithmusHier findest du auch noch Links:
Google @ C++.de
-
Dieser Thread wurde von Moderator/in evilissimo aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
CodeFinder schrieb:
...(nichts gegen QuickSort...aber der ist doch schon älter oder ?! ^^)
Und du glaubst das jedes Jahr ein neues, schnelleres Release erscheint.
-
AberHallo schrieb:
CodeFinder schrieb:
...(nichts gegen QuickSort...aber der ist doch schon älter oder ?! ^^)
Und du glaubst das jedes Jahr ein neues, schnelleres Release erscheint.
neee, keine neuere Version von QuickSort, sondern vollständig neue Algos
...MfG CodeFinder
-
Na dann setz dich hin und finde mal ganz schnell einen neuen Algo, wird ja auch mal wiede Zeit.
-
Ohne Einschränkungen gibt es keinen Alg. der besser als O(nlogn) sein kann. Von daher ist Quicksort schon gar nicht schlecht.
-
Jan schrieb:
Ohne Einschränkungen gibt es keinen Alg. der besser als O(nlogn) sein kann.
Immer dieses nebulöse "ohne Einschränkungen". Verrat doch mal genau, was nicht besser geht als O(nlogn).
-
Ich hab schon mal nen Algorithmus geproggt der hat das logon in 12ms geschaft.
-
Ich habe schonmal einen Sortieralgorithmus geschrieben der eine bereits sortierte Folge in O(n) sortieren kann.
-
Wie sieht es bei Sortieralgorithmen eigentlich mit der Parallelisierbarkeit aus? Sollte das nicht langsam relevant werden? Wie macht man das am Besten? Der Quicksort teilt das Problem ja schonmal auf, insofern hat man doch eigentlich recht gute Ausgangsbedingungen. Aber wie sorgt man dafür, dass die Teilprobleme ähnlich komplex sind? Oder geht man da komplett anders heran?
EDIT: Habe gerade in meinen Unterlagen einen parallelen Sortieralgorithmus gefunden, der auf Mergesort basiert. Da ist die Aufteilung natürlich einfacher und das geht wohl insgesamt recht einfach. Wie sieht es diesbezüglich aber mit Quicksort aus?
-
Das Sortieren ist sowieso total überbewertet. Wer muss den schon so oft riesen Datenmenge sortieren?
-
Z.b. ich ... sogar als Hobbyprogger. Hab ein Programm das Daten sucht und auflistet. Das gibt manchmal Listen mit 5'000+ an Elementen, die müssen dann nach unterschiedlichen vom User verlangten Kriterien sortiert werden. Das mache ich mit einem Mergesort. Wenn ich einen Bubblesort z.b. dafür verwenden würde ... puuuh ^^ ... das würde ja nie zu ende kommen
Grüssli
-
FachmannFürAlgorithmen schrieb:
Wer muss den schon so oft riesen Datenmenge sortieren?
Google!
-
Gregor schrieb:
Wie sieht es bei Sortieralgorithmen eigentlich mit der Parallelisierbarkeit aus? Sollte das nicht langsam relevant werden? Wie macht man das am Besten? Der Quicksort teilt das Problem ja schonmal auf, insofern hat man doch eigentlich recht gute Ausgangsbedingungen. Aber wie sorgt man dafür, dass die Teilprobleme ähnlich komplex sind? Oder geht man da komplett anders heran?
EDIT: Habe gerade in meinen Unterlagen einen parallelen Sortieralgorithmus gefunden, der auf Mergesort basiert. Da ist die Aufteilung natürlich einfacher und das geht wohl insgesamt recht einfach. Wie sieht es diesbezüglich aber mit Quicksort aus?
Mergesort ist IMO deshalb besser fuers Paralellisieren geeignet, da er die zu verarbeitenen Daten "gleichmaessig" aufteilt. Einn paralellisierten Quicksort kann ich mir schon vorstellen, aber in der "ersten Ebene" (d.h. vor dem ersten rekursiven Aufruf) muss die Arbeit nur von 1 CPU erledigt werden (zumindest meiner Meinung nach), danach koennen die beiden zerlegten Arrays auf 2 getrennte CPUs aufgeteilt werden:
Im Optimalfall sind bei jeder Teilung sind die Teilarrays gleich gross. Da die Teilarrays "gleichzeitig" abgearbeitet werden koennen, wuerd sich die Komplexitaet in jeder Rekursionsstufe halbieren:
n + (n/2) + (n/4) + (n/8) + .... = was fuer n->unendlich = n*log(n)
zumindest wenn ich mich jetzt nicht verrechnet hab. Damit wuerdest du in der gleichen Komplexitaetsklasse liegen wie der normale Quicksort.
EDIT: dummes Latex
-
Ohne jetzt deine Rechnung durchzugehen...
Der parallele Mergesort liegt zumindest in O(log n * log log n).
-
Evtl. interessiert dich das: (vergleich paralleler Mergesort und paralleler Quicksort)
www.cis.udel.edu/~pollock/372/f04/udtools.pptBTW gibts zum Thema "parallel Quicksort" erstaunlich viele Papers
-
vielleicht ganz interessant:
http://sortieralgorithmen.de/avlsort/index.html
