Mal angenommen, man hätte acht Elemente. Bubblesort würde hierfür ca. 7+6+5+4+3+2+1 Datenzugriffe brauchen (das sind 28). (Fange hinten an und vertausche, wenn das hintere Element größer, dann wiederhole dasselbe mit immer einem Element weiter hinten als Ziel, bis beim hintersten). Quicksort muß erst das mittlere Element(ein Zufälliges geht wohl langsamer) finden. Läuft es einmal über alle Elemente. Sind acht Zugriffe. Anschließend schiebt es in der linken und in der rechten Hälfte die Zeiger immer dann vor, wenn sie links kleiner oder rechts größer sind wie das Mittlere. Ist das nicht der Fall, vertauscht es beide Elemente. Das braucht auch acht Datenzugriffe. Geschweige denn, es geht nicht, dann muß es unter Umständen die Elemente in einem Array verschieben. Das braucht. Dann ruft sich Quicksort im Idealfall mit den vier linken und vier rechten Elementen selber auf und macht mit diesen dasselbe, wieder 16 Zugriffe. Dann ruft es in den Vieregruppen sich nochmal selber auf und vertauscht gegebenenfalls die Elemente. Das könnte man mit acht Zugriffen hinbringen. Macht also insgesamt vierzig Zugriffe. Findet man also nicht mit einer gescheiten Heuristik das mittlere Element, ist Bubblesort genauso schnell? Ich habe das nie richtig kapiert. Das es geht, ist klar. Die Frage ist nur wie schnell. Gehe davon aus, daß die Daten in einem Array vorliegen. Man könnte natürlich auch separierte Datensätze absteigend mit einer Kennzeichnung versehen, wie weit nach links sie zu sortieren sind. Aber da dann wieder drin rumzusuchen, braucht auch. (nicht signierter Beitrag von 06:01, 14. Jul 2016 (CEST) )