Welches ist euer Lieblings-Sortieralgorithmus?

[Senior Sanchez]

Holla *g*

Man merkt das es warm und Samstag ist, und da kam mir gerade die Idee für diese tolle Umfrage :uup:

Also mein Liebling ist bisher QuickSort, da ich den am einfachsten zu implementieren finde, wohingegen manche Algos wie RadixSort natürlich schon ziemlich cool sind ;)

Eben hatte ich mich an ShellSort probiert und es dann doch hinbekommen. Die Vorlage ausm Sedgewick hat da leider nicht so geholfen, da steckte irgendwo der Wurm drin.

[Coda]

Wieso Multiple-Choise wenns nur um den Liebling gehen soll?

Meine Antwort: Das was im speziellen Fall am schnellsten ist.

[Gast]

BubbleSort _. einfach und sehr effizient wenn korrenkt implekmentiert

[SamStone]

HeapSort. Warum is der nich in der Liste?

[Trap]

while(next_permutation(x.begin(),x.end())); // O(n!) :biggrin:

Introsort ist state-of-the-art für vergleichbasiertes Sortieren, warum ist das nicht in der Liste?

[Senior Sanchez]

Hmm, es gibt soviele Verfahren. Ich habe erstmal die gewählt die mir spontan eingefallen sind, aber wenn der Wunsch besteht kann man nach Benachrichtigung eines Mods sicherlich die Umfrage noch ändern ;)

@Coda
Dein zweiter Absatz beantwortet die erste Frage ;)
Man kann ja mehrere Lieblinge haben, bei denen es dann aber vom Anwendungszweck abhängt, welchen man nun wählt.

Ich sehe aber ein, dass die Frage vielleicht nicht ganz richtig gestellt ist ;)

[Monger]

Das ist ja von Natur aus ein nerdiges Forum, aber der Thread hier schießt den Vogel ab! :ugly:

Mir ist das völlig egal. Solange der Aufwand nahe n log( n ) bleibt, ist mir egal wie der Algorithmus heißt.

[Stone2001]

Für kleine n: Bubblesort!
Für große n: irgendwas mit O(n log n)

[Senior Sanchez]

Stone2001[/POST]']Für kleine n: Quicksort!
Für große n: irgendwas mit O(n log n)

Öhm, Quicksort ist O(n*log 2 n) ;)

[Senior Sanchez]

Monger[/POST]']Das ist ja von Natur aus ein nerdiges Forum, aber der Thread hier schießt den Vogel ab! :ugly:

Mir ist das völlig egal. Solange der Aufwand nahe n log( n ) bleibt, ist mir egal wie der Algorithmus heißt.

Ach naja, sooo schlimm nun auch wieder nicht ;)

Schlimmer war mal als ich im Kunstunterricht versucht habe mein mit Papier und Farbe gemaltes Bild abzuspeichern, aber auf dem Tisch habe ich kein Datei-Menu gefunden :D

Macht der Gewohnheit eben.

[Gast C++]

std::sort natürlich

[echter Linuxer]

unter Linux geht das vollst easy und efficient:

sort -a23 -xhts -klpe -x -bv -u <filename> | write -a 3 2 08809 -zu

[Senior Sanchez]

Man man man *g*
Es geht um Algorithmen, nicht um direkte Programme oder der simple Methodenaufruf ;)

Ich programmiere mir auch nicht ständig sowas, sondern nutze die sort-Methoden von Java, aber in diesem Fred gehts eben um konkrete Algorithmen.

[Stone2001]

Senior Sanchez[/POST]']Öhm, Quicksort ist O(n*log 2 n) ;)
Sorry, meinte Bubblesort! Aber seit wann ist Quicksort in O(n log n)? Er ist zwar meist so schnell (oder schneller) wie ein O(n log n) Algorithmus, der Worst-Case-Aufwand (was ja gerade das O-Kalkül angibt) liegt er immer noch bei O(n²).

[Coda]

Senior Sanchez[/POST]']Öhm, Quicksort ist O(n*log 2 n) ;)
Das kann gar nicht sein. Es gibt keine Konstanten in der O-Notation.

Senior Sanchez[/POST]']Man man man *g*
Es geht um Algorithmen, nicht um direkte Programme oder der simple Methodenaufruf ;)
Man sollte dumme Trolle von sinnvollen Posts unterscheiden können.

[Senior Sanchez]

Coda[/POST]']Das kann gar nicht sein. Es gibt keine Konstanten in der O-Notation.

Man sollte dumme Trolle von sinnvollen Posts unterscheiden können.

Welche Konstante? Ich sehe da keine. Ich habe da nur ne Komplexitätsklasse angegeben. Meinste die 2? Die gehörte mehr zum Logarithmus, aber im grunde kann man sie ja auch weglassen.

@Stone
Hast natürlich Recht, hatte mich verguggt. Im Mittel liegts bei O(n * log n)

[Coda]

Senior Sanchez[/POST]']Meinste die 2? Die gehörte mehr zum Logarithmus, aber im grunde kann man sie ja auch weglassen.
Macht man normal auch, weil es völlig egal ist was für ein Logarithmus es ist in der O-Notation.

[Gnafoo]

Coda[/POST]']Das kann gar nicht sein. Es gibt keine Konstanten in der O-Notation.
Mal davon abgesehen, dass er vermutlich O(n*log n) meinte. Natürlich gibt es die, warum auch nicht? f( n)=n liegt z.B. in O(n+7) oder in O( n) oder in O( n²+wurzel(2)). Sonderlich sinnvoll ist das sicherlich nicht, aber durchaus korrekt.

[Senior Sanchez]

KK, wieder was gelernt ;)

[Senior Sanchez]

Der Tod[/POST]']Mal davon abgesehen, dass er vermutlich O(n*log n) meinte. Natürlich gibt es die, warum auch nicht? f( n)=n liegt z.B. in O(n+7) oder in O( n) oder in O( n²+wurzel(2)). Sonderlich sinnvoll ist das sicherlich nicht, aber durchaus korrekt.

Naja, es gibt ne konstante Laufzeit in der O-Notation (eben O(1)). Aber O(n) ist ja völlig legitim mit linearer Laufzeit, aber O(n² + wurzel(2)) würde man denke ich mehr der Komplexitätsklasse O(n²) zuordnen.

[Gnafoo]

Wie gesagt. Es ist korrekt, aber wenig sinnvoll, weil O( n) und O(n+7) eben die selben Mengen darstellen und man es deshalb lieber als O( n) angibt. O(n²+wurzel(2)) ist ebenso genau die selbe Menge von Funktionen wie O(n²).

Theorie ist doch was feines ;D.

[Senior Sanchez]

Ja, natürlich ist das so, keine Frage und dass das richtig ist, stimmt auch.

Nur meist kategorisiert man ja in die diversen Klassen.

[Neomi]

Mein Lieblingsalgorithmus ist der Heapsort (mit Bottom-Up-Optimierung), da er keinen Worst-Case kennt. Bei kleineren Arrays nehme ich auch mal simplere Verfahren wie z.B. Insertionsort.

Von den wählbaren Algorithmen gefällt mir Mergesort ganz gut. Leider kein In-Place-Sorter, dafür aber sehr schnell und (bei großen Arrays) leicht auf mehrere CPU-Kerne verteilbar.

Eigentlich ist jeder Algorithmus gut, der jedem anderen in mindestens einem Fall überlegen ist.

[CannedCaptain]

http://www.thaleweb.de/start/stuff/sortIt/

Hab ich im Rahmen meiner Vordiplomsvorbereitung im Nebenfach Info geschrieben. Ist eine Java 1.5 Anwendung, die Sortieralgos graphisch in einem Player visualisiert.

[Senior Sanchez]

CannedCaptain[/POST]']http://www.thaleweb.de/start/stuff/sortIt/

Hab ich im Rahmen meiner Vordiplomsvorbereitung im Nebenfach Info geschrieben. Ist eine Java 1.5 Anwendung, die Sortieralgos graphisch in einem Player visualisiert.

Schaut ganz nett aus :)

Aber füge in deine sortIt.bat bitte mal noch nen -cp . ein ;)
Standardmäßig ist nämlich die Klasse nicht im Java Classpath.

[CannedCaptain]

Hatte kein Windows, um das zu testen.
[x] Mergesort

[Senior Sanchez]

CannedCaptain[/POST]']Hatte kein Windows, um das zu testen.
[x] Mergesort

Warum eigentlich Mergesort?

[registrierter Gast]

[x] Insertionsort

Ist so schön vorhersagbar in Vergleichen und Wertzuweisungen =), auch wenn er natürlich nicht zu den Schnellsten gehört.

[Senior Sanchez]

registrierter Gast[/POST]'][x] Insertionsort

Ist so schön vorhersagbar in Vergleichen und Wertzuweisungen =), auch wenn er natürlich nicht zu den Schnellsten gehört.

Das hängt ja auch wieder von der Situation ab ;) InsertionSort kann extrem schnell sein, aber dazu muss natürlich die Folge stimmen (am besten schon fast sortiert, dann läufts linear ab ;) )

[CannedCaptain]

Weil Mergesort entgegen der meisten Sortieralgorithmen einen äußerst interessanten Verlauf der Ordnung hat, wie Du ja leicht im oberen Diagramm meines Programms ersehen kannst. Ich habe eher eine andere Frage:
Kannst Du mir einen Tipp geben, wie ich diese Anwendung on the fly auf Windowsrechner zum laufen bringe. So Marke Doppelklick bei willkürlichen Installationspfad usw.
Hast Du Ideen, welche Algos noch realisert werden könnten.

[Senior Sanchez]

CannedCaptain[/POST]']Weil Mergesort entgegen der meisten Sortieralgorithmen einen äußerst interessanten Verlauf der Ordnung hat, wie Du ja leicht im oberen Diagramm meines Programms ersehen kannst. Ich habe eher eine andere Frage:
Kannst Du mir einen Tipp geben, wie ich diese Anwendung on the fly auf Windowsrechner zum laufen bringe. So Marke Doppelklick bei willkürlichen Installationspfad usw.
Hast Du Ideen, welche Algos noch realisert werden könnten.

Da gibts mehrere Varianten.
Ab Java 1.4 kann ein executable Jar-File direkt per Doppelklick gestartet werden, wenn eben mind. ne 1.4er JVM auf dem Rechner ist.
Dazu musste das Jar-Archiv am besten mit jar -cfvm bauen (komprimiert, du kannst nen output file angeben, verbose mode ist an und m bedeutet dass du ein manifest anfügst). Per Manifest kannste eben die Main-Klasse festlegen, die dann beim Doppelklick ausgeführt wird.

Ne andere Möglichkeit die sich für On-The-Fly anbietet ist Java Web Start. Der Nutzer muss es installiert haben (ab 1.4 glaube ich automatisch dabei) und so kann der Nutzer dann im Internet nen jnlp-File (java network launcher protocol) anklicken, woraufhin Java Web Start diese jnlp-Datei interpretiert, benötigte Dateien herunterlädt und die Applikation startet. Java WS kann dann auch die Anwendung auf dem Desktop per Verknüpfung startbar machen.

Als Algos würde ich auf jeden Fall noch Radixsort vorschlagen, der ist interessant. Shellsort ist ja nen gepimptes Insertionsort und Intro-Sort nen verbesserter Quicksort der auf alternative Verfahren zurückgreifen kann. Digitales Sortieren könnte auch noch interessant sein.

PS: Ich würde die Anzahl der zu sortierenden Elemente noch höher als 150 anlegen. Momentan ergibt sich zwischen BubbleSort und QuickSort überhaupt kein Unterschied, zeitlich gesehen. Beide brauchen selbst auf meinem nciht mehr ganz frischen Rechner (Athlon XP 1800+, 1.5 GB RAM) 0.0 ms.

[CannedCaptain]

Das Problem ist der Worst case des Bubble Sort. Das ist der Grund warum zurzeit noch 150 drin ist. denn 150^2 * 150 Zustände. Ist schon eine immense Speichermenge.

[Coda]

Hm Speichermenge? Bubblesort ist doch In-Place oder nicht? :|

[Senior Sanchez]

Coda[/POST]']Hm Speichermenge? Bubblesort ist doch In-Place oder nicht? :|

Jo, eben ;)

Und deine Rechnung 150^2 * 150 kapier ich auch nicht. Seit wann hat BubbleSort ne kubische Laufzeit?

PS: 150^2 ist doch ansich überhaupt nix. Da kannste ruhig auf 1000 oder 10.000 hochgehen.

[CannedCaptain]

Das Programm merkt sich jeden Zustand, den das System je hatte. Im worst case sind das 150^2 Zustände, die jeweils mit 150 Slots gespeichert werden. Wie auch sonst will man einen Player realisieren bei dem man zurückspulen kann? Zudem müssen noch 150^2-Slots für die Erfassung des Korrelationskoeffizienten verpulvert werden. Der Sortieralgo ist inplace, das Programm aber nicht. Da sind dann eher 128MB RAM getrasht als Du denkst. Und da dieses Programm den Algo visualisieren soll, zu Lehrzwecken ist eine große Anzahl auch gar net erforderlich. Wenn man das System on the Fly rechnen wollte, dann bräuchte man eine bijektive Abbildung zu jedem Zustand. Die liegt nicht vor => jeder Zustand muss im Speicher liegen.

[Senior Sanchez]

CannedCaptain[/POST]']Das Programm merkt sich jeden Zustand, den das System je hatte. Im worst case sind das 150^2 Zustände, die jeweils mit 150 Slots gespeichert werden. Wie auch sonst will man einen Player realisieren bei dem man zurückspulen kann? Zudem müssen noch 150^2-Slots für die Erfassung des Korrelationskoeffizienten verpulvert werden. Der Sortieralgo ist inplace, das Programm aber nicht.

Achso, ic.

Haste mal profiled um zu sehen wieviel Speicher es insgesamt schluckt?

[Wanginator]

Ich benutze je nachdem welches man gerade benötigt oder einfach eine API-Implementation :D

Schön finde ich aber Quicksort zwecks einfacher algorithmischer Deklaration, Merge-Sort als stabiles Verfahren und Standardbeispiel für Divide-and-Conquer. Persönlich finde ich aber Heapsort am effektivsten, ist aber leider nicht mit aufgelistet...

[Senior Sanchez]

Wanginator[/POST]']Ich benutze je nachdem welches man gerade benötigt oder einfach eine API-Implementation :D

Schön finde ich aber Quicksort zwecks einfacher algorithmischer Deklaration, Merge-Sort als stabiles Verfahren und Standardbeispiel für Divide-and-Conquer. Persönlich finde ich aber Heapsort am effektivsten, ist aber leider nicht mit aufgelistet...

Naja, ich implementiere mir auch nicht ständig ne neue Sortierfunktion sondern nutze die der API ;)

Quicksort ist aber auch ein Standardbeispiel für Divide-and-Conquer, jedenfalls bei einer passablen Folge.

Hmm, da so viele Heapsort mögen, sage ich mal nem Moderator Bescheid, ob er noch Heapsort hinzufügen könnte.

[Trap]

CannedCaptain[/POST]']Das Programm merkt sich jeden Zustand, den das System je hatte. Im worst case sind das 150^2 Zustände, die jeweils mit 150 Slots gespeichert werden. Wie auch sonst will man einen Player realisieren bei dem man zurückspulen kann?
Man könnte die Sortieralgorithmen so implementieren, dass sie nur x Schritte machen, sich die Anfangsbelegung merken und bei jedem hin- und herspulen von der Anfangsbelegung bis zur entsprechenden Stelle komplett neu sortieren. Dann gehen sicher auch >1000 Elemente.

[CannedCaptain]

Ich weiß ja eure Tipps zu schätzen. Etwas zu mir: Ich bin Physiker, Physiker lieben deterministisch bestimmte System, das ist ein Sortieralgo aber nicht. Es widerspricht einfach meiner Überzeugung, wenn ich ein Tool zu
Visualisierung von Sortieralgos schreibe, dass zwischen den Zuständen interpoliert wird. Man soll damit nicht sortieren, sondern lernen, wie der Algo die Elemente vertauscht, Betonung auf das wie. Da ist eine Interpolation von Zuständen nicht hilfreich, denn es soll zurückverfolgbar sein und jeder Zustand schlüssig aus dem anderen folgen. Es gibt nun mal keine Abb, die aus der Ordnung eindeutig in eine deterministische festgelegte Unordnung abbildet. (Die Unordnung sieht ja jedesmal anders aus). Der Algo soll also nicht effizient, sondern konsistent in jedem Zustand sein - das war Zielsetzung.

[PrakashKC]

Neomi[/POST]']
Von den wählbaren Algorithmen gefällt mir Mergesort ganz gut. Leider kein In-Place-Sorter, dafür aber sehr schnell und (bei großen Arrays) leicht auf mehrere CPU-Kerne verteilbar.


Natürlich läßt sich Mergesort in-situ implementieren, nur muß man dafür mehr Hirn investieren...

[Senior Sanchez]

PrakashKC[/POST]']Natürlich läßt sich Mergesort in-situ implementieren, nur muß man dafür mehr Hirn investieren...

Wenn die sortierende Menge eine verkettete Liste ist, sollte das relativ einfach sein.

Für Arrays wirds aber wohl schwieriger.

[Neomi]

PrakashKC[/POST]']Natürlich läßt sich Mergesort in-situ implementieren, nur muß man dafür mehr Hirn investieren...

... und man erkauft sich den gewonnenen Speicherplatz sehr teuer mit Rechenzeit. Ich kann es auch anders formulieren: Mergesort ist leider kein In-Place-Sorter oder nicht sehr schnell.

[ethrandil]

Heapsort.
Ich sag nur: WorstCase, Wööörst Käise.

- eth

[CannedCaptain]

linear ordered Mengen mit Heapsort sind nicht sher effizient, dafür das jeder andere algo da O(n) braucht.

[ethrandil]

CannedCaptain[/POST]']linear ordered Mengen mit Heapsort sind nicht sher effizient, dafür das jeder andere algo da O(n) braucht.
Das ist eine rein irrationale Antwort gewesen. Ich mag Heapsort halt.

:P

- eth

Oh nein, ich war lange nicht mehr hier. Gibt es den :bäh:-Smiley nicht mehr? Ich finde den besser, weil der :P -Smiley immer so fies aussieht...

[PH4Real]

Ich find Mergesort ganz schick: Stabil und relativ schnell.

Ein ganz witziges und kurioses (zumindest bei der Musik :biggrin: ) Video zum Sortieren hatte ich beim ccc mal gefunden:

http://chaosradio.ccc.de/ctv027.html

Achja... weiß nicht, ob man Introsort wirklich als eigenständigen Sortieralgorithmus aufführen sollte. Ist eigentlich ja genauso wie Quicksort, nur dass er immer vorher guckt, ob er weiter mit Quicksort sortieren soll oder z.B. einen Heapsort anwendet.

Für mich ist das eher eine intelligente Zusammensetzung von bestehenden Algorithmen.

[orda]

Bubble, weil er so schön einfach aber auch uneffizient (wohl am uneffizientesten, oder?) ist und Quicksort, weil es der einzige Sortieralgo ist, den ich neben Bubble kenne...

so long...

[Coda]

ethrandil[/POST]']Oh nein, ich war lange nicht mehr hier. Gibt es den :bäh:-Smiley nicht mehr? Ich finde den besser, weil der :P -Smiley immer so fies aussieht...
:tongue:

Bissel arg OT ;)

[Senior Sanchez]

PH4Real[/POST]']
Achja... weiß nicht, ob man Introsort wirklich als eigenständigen Sortieralgorithmus aufführen sollte. Ist eigentlich ja genauso wie Quicksort, nur dass er immer vorher guckt, ob er weiter mit Quicksort sortieren soll oder z.B. einen Heapsort anwendet.

Für mich ist das eher eine intelligente Zusammensetzung von bestehenden Algorithmen.

Jo, hatte ich ja auch schon geschrieben, was es eigentlich ist. Da der Wunsch kam es mit aufzunehmen ist es aufgenommen worden zumal ja auch noch nen bissl algorithmische Leistung mehr dazu gehört: Man muss ja versuchen anhand der Menge festzustellen welcher Algorithmus nun der bessere wäre, quasi ne Art Bewertungsfunktion und da ist ja auch nen bissl Anspruch dabei ;)


Wenn man streng wäre, dürfte man dann ja ansich auch Shellsort nicht so ganz zulassen, weil es mehr nen aufgemöbeltes Insertionsort ist.

[Matti]

Ich hab Bubble-Sort etwas getuned, so daß es auch im Worst-Case (eine verkehrt herum sortierte Liste) halbwegs schnell ist:


procedure PSBSort(var A: array of Integer);
var
I, L, T: Integer;
ok:boolean;
begin
L:=High(A)-Low(A)+1;
repeat
if L>1 then begin
L:=L div 2;
end;
ok:=true;
for i:=Low(A) to High(A)-L do begin
if A[I] > A[I+L] then
begin
ok:=false;
T := A[I];
A[I] := A[I+L];
A[I+L] := T;
end;
end;
until (l=1) and ok;
end;


Ich hab den Algorithmus "Pre-Sorted Bubble Sort" genannt, weil in den ersten Schleifen-Durchläufen, wo L>1 ist eine schnelle Vor-Sortierung stattfindet.

Das ist mein Lieblings-Algorithmus, denn er ist fast so einfach wie Bubble-Sort und braucht sich von der Geschwindigkeit her nicht zu verstecken :)

[Coda]

Aber auch nur bei sehr kleinen Mengen.