Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
sortieralgorithmen
ich hab hier einen netten link gefunden, mit dem man grafisch mitverfolgen kann, wie die sortieralgorithmen funktionieren - es werden komischerweise genau die fünf angeboten, die wir auch gemacht haben 
- bis auf heap sort, das kann aber nicht so wie diese visualisiert werden.
puh, ja, schon geniales stück technologie, aber diesem blöden quicksort-kram versteh ich noch net… das ding is mir selbst mit animation und einzelschritt zu schnell… der rest geht ja ganz einfach (und dementsprechend ineffizient)
ich werd’s mir einfach nochmal genauer anschauen (und vielleicht find ich ja was im “skript” dazu lol)
ich bin jetzt erst zum programmieren der sortierverfahren gekommen und quicksort bereitet mir echte probleme. in den ganzen beschreibungen wird nie erwaehnt, was man macht, wenn auf einer seite des pivotelements z. b. 3 felder uebrig sind, die auf die andere seite muessten, auf der anderen seite aber nichts getauscht werden muss.
das muss ich irgendwann nochmal in ruhe durchdenken…
wenn du da was gefunden hast, bist du sicher so fit mit dem quicksort, dass wir und vllt. mal zusammensetzen sollten :cheesy:
natuerlich, kein problem.
ich hoffe, dass ich bis dahin auch das unverstaendliche gecheckt habe.
Mit der Quicksort Ausführung in Stoyans Folien bin ich auch nicht sonderlich gut klar gekommen. Das Beispiel, das er benutzt hat, um den Algorithmus zu demonstrieren, ist IMHO schlecht gewählt, da das Pivot-Element schon an der richtigen Stelle steht und einem (mir zumindest) somit suggeriert wird, dass das Pivot-Element nicht mit sortiert werden muss. Und dem Java-Code-Wirrwarr, das dann am Schluss noch folgte ist dank der ausgezeichneten Übersicht ja auch kinderleicht zu durchschauen (Ironie).
Lange Rede gar kein Sinn.
Schaut einfach mal bei http://www.grundlagen.delphi-source.de/algorithmen/sortieren/quicksort.shtml vorbei. Ist zwar Delphi Code, aber das kann auch jemand lesen/verstehen, der kein Delphi oder Pascal kennt.
ich geb auch noch einen link zum besten:
hier sind die algorithmen in C implementiert.
http://www.pronix.de/C/standard_C/c_programmierung_25.shtml
das tutorial ist übrigens schweinisch gut, wenn ich bloss noch kein C könnte
olé, ich habs endlich geschafft! danke fuer das tolle visualisierende java-applet, nachdem ich mir das nochmal eine halbe stunde total duemmlich angeschaut habe (pro step ewig gebraucht, um ihn zu analysieren, warum er zustande kam und was er genau macht), hats endlich geschnackelt. der ist bei mir auch sauschnell, der algorithmus, auch wenn ich ihn ziemlich ineffizient, dafuer aber relativ uebersichtlich (wenn man in dem kontext von uebersichtlichkeit sprechen kann) implementiert habe.
irgendwann am wochenende probiere ich mich dann noch an heapsort und dann ist endlich schluss damit…
update:
jetzt hab ich auch heapsort geschafft. aber nur mit hilfe eines visualisierenden applets wiedermal. da das oben gepostete kein heapsort gezeigt hat, hab ich selber eins gesucht:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/heapsort.html
viel spass an die, die das noch machen wollen…
Hat einer von euch vielleicht eine Liste mit dem Sortieraufwand, Suchaufwand,… für die ganzen Algorithmen?
Denn in der Vorlesung ist nur teilweise was besprochen worden.
von pessimisten und optimisten
http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/problem.htm
(hab ich den link schon mal gepostet? hmm…)
boah =) ESMAJ jetzt bin ich platt 
also ich peil den KMP-algorithmus einfach nicht. der vielleicht schwierigere (?) boyermoore ist mir verstaendlicher. kann jemand eine erklaerung dazu posten?
Glaubt ihr wirklich dass die drankommen könnten.In der Übung war von denen kein Wort zu hören!
Hab jetzt schon soviel Algorithmen im Kopf dass kein PlaTZ ist!
so geht’s mir auch. ich haette lieber weniger algos, die aber dafuer gescheit im kopf!
kmp-algorithmus, was denn das, denk und hoff doch mal, dass der nicht drankommt
HILFEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
imho ist der mergesort algo von schmidt&co (uebung 4) falsch implementiert worden.
bei dem unten geposteten link zu den sortierverfahren ist mergesort auch der mit abstand zweitschnellste (um den faktor 100-1000, bei einer array-groesse von 100000).
link: http://math.hws.edu/TMCM/java/xSortLab/
bei schmidt&co haut ihr loesungsvorschlag ziemlich exponentiell ab…
wieso muss ich erst das array solange halbieren bis alle elemente einzeln dastehen um sie dann wieder paarweise zusammenzufuegen?
siehe uebung4 loesungsvorschlag aufgabe 13 fuer mergesort.
Ja, auf meinem Palm, der Sortieren ganz toll graphisch darstellt, sieht MergeSort auch ein wenig anders aus. Gesplittet wird da nichts …
Und besonders langsam ist es auch nicht …
Was in besonders wenigen Schritten zu gehen scheint ist “Radixsort” und “Shellsort” (was auch immer das sein mag g)
Wurscht … darum geht es morgen bestimmt nicht 