Quicksort - theorie

[rsplisu]

Noch eine Frage:
Wenn man nur 2 Felder hat,

[4]-5

wobei 4 die Mitte ist. Hi springt, dann auf auf die A(Hi)(4), dadurch werden die Felder Lo und Hi getauscht und es geschieht Dec(hi) und Inc(lo) also A(Hi)(4) und A(Lo)(5). Damit uberlaufen sich Lo und Hi und das Programm endet die Arbeit, weil es nur je ein Feld gibt.

Erklaer ich das richtig?


... mdl Abiturstesss.... :/

[Uwe Raabe]

Zitat von rsplisu:

Wenn man nur 2 Felder hat,

[4]-5

wobei 4 die Mitte ist. Hi springt, dann auf auf die A(Hi)(4), dadurch werden die Felder Lo und Hi getauscht und es geschieht Dec(hi) und Inc(lo) also A(Hi)(4) und A(Lo)(5). Damit uberlaufen sich Lo und Hi und das Programm endet die Arbeit, weil es nur je ein Feld gibt.

So in etwa. In dem Fall sind iLo=0 und iHi=1. Die erste while-Schleife läuft nicht, da A[Lo] = mid ist. Die zweite wird einmal durchlaufen. Danach sind Lo = 0 = Hi und die if-Bedingung schlägt zu, tauscht dabei aber nur A[0] mit A[0], was ja nichts ändert. Dann haben wir nach Inc(Lo) und Dec(Hi) Lo = 1 und Hi = -1. Das bringt die repeat-Schleife zum Abbruch und die rekursiven Aufrufe erfolgen auch nicht.

[Delphi-Laie]

Zitat von sx2008:

Um Quicksort zu verstehen muss man den Algorithmus visuell betrachten.
https://www.youtube.com/watch?v=ywWBy6J5gz8 (Ton leise stellen, sonst nervt es)

Oder es sich in meinem Sortierkino anschauen.