A gyorsrendezés (quicksort)

Adott egy n elemű M tömb. Rendezzük növekvő sorrendbe az elemeit!

A megvalósítás gondolatmenete:

úgy rendezgetjük a tömböt, hogy az elemek cserélgetésével két olyan részre osztjuk fel, hogy a baloldali rész egy meghatározott (mi határozzuk meg) értéknél csupa kisebb, a jobboldali rész pedig csupa nagyobb elemet tartalmaz. Miután ezzel megvagyunk, akkor hasonlóan alkalmazzuk ezt az eljárást a baloldali és a jobboldali részre. Ezeket a részeket újra felosztva a legvégén egyelemű résztömbök keletkeznek, és ezzel a teljes tömb rendezett lesz. Logikus, hogy mivel ugyanazzal a módszerrel rendezzük az egyes részeket, rekurziót fogunk használni. (Ez az egyik leghatékonyabb rendezés.)

Az algoritmus mondatszerű leírása:

Eljárás quicksort_rendezes:

Be: M

bal = kezdet

jobb = vege

kozep = (bal+jobb) Div 2

tampont = M(kozep)

Ciklus Amíg bal <= jobb

Ciklus Amíg M(bal) < tampont

bal = bal + 1

Ciklus vége

Ciklus Amíg M(jobb) > tampont

jobb = jobb – 1

Ciklus vége

Ha bal <= jobb Akkor

Csere(M(bal), M(jobb))

Elágazás vége

Ciklus vége

Ha kezdet < jobb Akkor

quicksort(kezdet, jobb)

Elágazás vége

Ha bal < vege Akkor

quicksort (Bal, Vége)

Elágazás vége

Eljárás vége

Feladat:

A csoportban tanuló diákok neveit egy rendezetlen tömbben tároljuk. Rendezzük ezeket ABC sorrendbe!

Program rendetrak3;

Eljárás quicksort(bal, jobb)

tampont = nevsor((bal + jobb) div 2)

i = bal

j = jobb

Ciklus Amíg i < = j

Ciklus Amíg nevsor(i) < tampont

i = i + 1

Ciklus vége

Ciklus Amíg nevsor(j) > tampont

j = j – 1

Ciklus vége

Ha i < = j Akkor

munka = nevsor(i)

nevsor(i) = nevsor(j)

nevsor(j) = munka

i = i + 1;

j = j – 1;

Elágazás vége

Ciklus vége

Ha bal < j Akkor

quicksort(bal, j)

Elágazás vége

Ha i < jobb Akkor

quicksort(i, jobb)

Elágazás vége

Eljárás vége

Quicksort ( 1, N );

Program vége.

Házi feladat:

Töltsünk fel véletlenszerűen egy N elemű tömböt 1 és 100 közötti számokkal, majd rendezzük gyorsrendezéssel!