Thema: quick_sort -> nicht immer quick, wenn das mittlere Element d
ein problem mit dem Quick_Sort Algo:<P>erstmal Zitat:<P>5 - 6 - 9 - 7 - 4 - 10 - 8<P>"Quicksort arbeitet ebenfalls mit dem Tauschen von Elementen, allerdings werden die Elemente auf intiligentere Weise (als bei Bubble sort) ausgewält. QS beginnt damit die zu sortierenden Elemnte in 2 Hälften aufzuteilen. Dazu wird das mittlere element als Referenz ausgewählt. (in unserem Falle die 7) Jetzt wird die Folge von vorne durchsucht, bis ein Element gefunden wird, das größer ist als das Referenzelement (9). Gleichzeitig wird die Folge von hinten durchsuchte, bis ein Element gefunden wird das kleiner als das Referenzelement ist (4). Diese beiden Elemente werden vertauscht.<P>5 - 6 - 4 - 7 - 9 - 10 - 8<P>Danach werden die Folgen von Vorne und hinten weiter durchsucht und die gefundenen Elemente paarweise ausgetauscht, bis man sich irgendwo trifft (was in unserem Fall zufällig direkt bei der 7 der Fall ist) Danach werden die beiden Hälften links und rechts des Treffpunkts für sich nach dem gelichen Verfahren sortiert:<P>5 - 4 - 6 - 7 - 9 - 8 - 10<P>Und so weiter, bis die elemten sortiert sind.<P>4 - 5 - 6 - 7 - 9 - 8 - 10<P>4 - 5 - 6 - 7 - 8 - 9 - 10<P>"<P>Obwohl einem ja so ziemlich alle Programmiersprachen sort() funktionen zur Verfügung stellen, möcht ich so was mal nach programmieren. <P>Das Verfahren ist ja gut nachvollziebar und umsetzbar, bis auf einen Punk. Was ist wenn die Zahl in der mitte die höchste Zahl ist?<P>z.B. <P>3 - 9 - 3 - 10 - 4 - 7 - 2<P>Dann such ich von vorne, bis ich _was_ finde. Zumindest nix höheres. Ich könnte mir ja das letzte element nehmen welches ich gefunden habe und das als Referenzwert nehmen. Was ist aber, wenn der letzte Referenzwert zufälligerweise das kleinste element (in dem Fall jetzt 2). Dann mach ich das Spiel andersrum und such wieder von Hinten bis ich was niedrigesres Finde. Find ich aber nicht. Also nehm ich den ersten Wert als Referenz, in dem Fall die 3 und such wieder von hinten nach was niedrigerem.<P>Wow, dann klappst endlich mal, sogar gleich beim ersten. Die kann ich dann vertauschen.<P>2 - 9 - 3 - 10 - 4 - 7 - 3<P>dann guck ich von vorne nach was höherem, die 9.<P>Vertauschen:<P>2 - 3 - 3 - 10 - 4 - 8 - 9<P>usw:<P>meine Frage, die quick_sort wird als sehr schnell gehandelt. Ist das was ich gerade mit viel zu vielen Worten probiert habe zu beschreiben richtig so, oder gehts auch einfacher?<P>thx, sel.