Programozás‎ > ‎Rendezések‎ > ‎

Gyorsrendezés

A gyorsrendezés az összefésülő rendezés egy lehetséges továbbfejlesztett változata. Előnye az összefésülő rendezéshez képest az, hogy nem szükséges egy második tömb az összefésülésekhez, vagyis feleakkora a memóriaigénye. Általában rekurzív módon szokás megfogalmazni.

Gondolat

A tömböt az első eleme szerint (helyben) szétválogatjuk. Ha az első elem értéke X, akkor a tömb elejére kerülnek az X-nél nem nagyobb, a végére pedig az X-nél nem kisebb elemek, és "középre" X. Ezután az X-nél kisebb és az X-nél nagyobb elemeket rekurzív rendezzük. Ez a megközelítés akkor rendez gyorsan, ha a szétválogatások "nagyjából" egyenlő részekre vágják az aktuális tömböket. A "rossz" bemeneteket úgy szokás kiküszöbölni, hogy a gyorsrendezés előtt összekeverjük a tömböt (ez lineáris algoritmussal megtehető.)


Algoritmus

Gyorsrendezés

gyorsrendez(a, E, U):
    kever(a, E, U)
    rendez(a, E, U)
eljárás vége


rendez(a, E, U):
    Ha E < U akkor
        K = szétválogat(a, E, U)
        rendez(a, E, K-1)
        rendez(a, K+1, U)
    Elágazás vége
eljárás vége


Szétválogatás

szétválogat(a, E, U):
    pivot := a[E]
    i := E; j := U+1
    Ciklus amíg i < j
        Ciklus
            i := i+1
        amíg a[i] < pivot és i < U
        Ciklus
            j := j - 1
        amíg a[j] > pivot és j > E
        Ha i < j akkor csere(a, i, j)
    Ciklus vége
    csere(a, E, j)
    szétválogat := j
eljárás vége

Keverés

kever(a, E , U):
    Ciklus i := E-től (U-1)-ig
        k := Véletlen(i, U)
        Csere(a, i, k)
    Ciklus vége
eljárás vége