Gyorsrendezés helyben

A gyorsrendezés előadáson bemutatott változata nem helyben rendezést valósít meg. Vagyis nem egy meglévő listában cserélgeti az elemeket, hanem új listát állít elő. Ennek az algoritmusnak létezik egy helyben rendezős megvalósítása is, amely azonban bonyolultabb az előadáson bemutatottnál. Cserébe viszont nem épít rengeteg segédlistát futás közben, és így sokkal gyorsabb tud lenni.

A helyben rendezéshez szükségünk van egy helyben szétválogató algoritmusra, amelynek működése az alábbi. A feladatunk: adott egy lista, benne vegyesen kék és piros golyókkal. A kékeket előre, a pirosakat hátra kell gyűjteni.

start következő

Lényege: a lista két végéről indulnak indexek.
Megkeressük balról az első pirosat, jobbról kéket, és megcseréljük őket.
Ezt folytatjuk, amíg a két index nem találkozik.

A működés kicsit részletesebben:

1. Indítunk két indexet, egyiket a lista elejéről (bal), másikat a végéről (jobb).
2. Balt addig növeljük, amíg kék golyóra mutat. Így találunk egy piros golyót.
3. Jobbat addig csökkentjük, amíg piros golyóra mutat. Így találunk egy kék golyót.
4. Megcseréljük a talált pirosat a kékkel, és így folytatjuk, amíg a két index „össze nem ér”.

def szetvalogat(lista):
    bal = 0
    jobb = len(lista) - 1
    
    while bal < jobb:
        while bal < jobb and lista[bal] != 1:  # 'pirosat' keres
            bal += 1
        while bal < jobb and lista[jobb] != 0: # 'kéket' keres
            jobb -= 1
        if bal < jobb:
            temp = lista[bal]   # csere
            lista[bal] = lista[jobb]
            lista[jobb] = temp
            bal += 1
            jobb -= 1           # egyből a következőkre

Minden csere után természetesen növelhetjük a balt és csökkenthetjük a jobbat eggyel, hiszen a csere hatására a bal index alá kék, a jobb index alá pedig piros golyó kerül. Fontos, hogy a keresések során is figyeljük, hogy nem értek-e össze az indexek; ez előfordulhat ugyanis bármelyik pillanatban. (Ezzel azt is ellenőrizzük, hogy nem érünk-e a lista végére valamelyik indexszel. Az is lehetséges, ha a lista csak kék vagy csak piros golyót tartalmaz.)

Vagyis pl. a kereső ciklusok megállhatnak így:

Ha megcseréljük a tomb[bal] és a tomb[jobb] elemet:

Akkor a csere után a két indexet gondolkodás nélkül növelhetjük és csökkenthetjük:

És innen folytatjuk megint piros-kék kereséssel.

A helyben rendező algoritmus működését az alábbi animáció szemlélteti.

start következő folyamatos

Érdemes megfigyelni a következőt: ha a vezérelem elé rendeztük a kisebbeket, mögé a nagyobbakat, az azt jelenti, hogy a vezérelem már a végleges helyére kerül. Ugyanis ha nála kisebből van emennyi (előtte), nála nagyobból meg amannyi (utána), akkor ezek a számok egyben a vezérelem helyét is meghatározzák. Hiszen ezek (emennyi és amannyi) nem fognak már változni.

A klasszikus megvalósítás a fentiek alapján, helyben rendezve a listát:

def gyorsrendez(lista, eleje, vege):
    vezer = lista[(eleje + vege) // 2]  # vezérelem: középső
    bal = eleje
    jobb = vege
    while bal <= jobb:                  # piros/kék válogatás
        while lista[bal] < vezer:
            bal += 1
        while lista[jobb] > vezer:
            jobb -= 1
        if bal <= jobb:
            tmp = lista[bal]
            lista[bal] = lista[jobb]
            lista[jobb] = tmp
            bal += 1
            jobb -= 1
    
    if eleje < jobb:
        gyorsrendez(lista, eleje, jobb) # rekurzió
    if bal < vege:
        gyorsrendez(lista, bal, vege)

Az algoritmus részei: a while bal <= jobb ciklus végzi a szétválogatást; utána pedig az utolsó két sorban láthatók a rekurzív hívások, amelyek rendezik a lista így keletkezett két részét.

A bal <= jobb ciklus végefelé a bal és a jobb index is a már helyre került vezérelemnél áll. A belső, piros-kék keresős ciklusok megállnak a megtalált vezérelemnél is, hiszen elem<vezér és elem>vezér kifejezések a feltételeik. (Tehát a pirosat kereső ciklusnak a vezérelem pirosnak számít, a kéket kereső ciklusnak a vezérelem kéknek számít. Ha a vezérelem elöl van, akkor egy cserében hátrébb kerül, ha hátul van, akkor egy cserében előrébb kerül. Előfordulhat, hogy ide-oda pattog, de végül középre fog kerülni.) A ciklus futása után egy ilyen állapot lesz a listában:

Ezután a bal += 1 és jobb -= 1 utasítással még módosítjuk az indexeket (lásd a szétválogatási feladatot). Így bal és jobb a rendezendő két részintervallum széleit is jelzik, és az eddigiektől eltérően jobb < bal igaz:

Ezért van az, hogy a két rekurzívan rendezendő listarészletet a [eleje,jobb] és az [bal,vege] indexek adják, zárt intervallumban.

Az előzőektől eltérően ennek a függvénynek nem a lista méretét kell megadni, hanem a rendezendő intervallum alsó és felső határát. De ez nem gond, hiszen egy egysoros függvénnyel ugyanolyan formában használhatjuk ezt is:

def gyorsrendez_indit(lista):
    gyorsrendez(lista, 0, len(lista)-1)

Az indító függvény, és az egyes rekurzív hívások elég sokat passzolgatják egymásnak a lista referenciáját. Ez programozás szempontjából elég kényelmetlen. A Python azonban megengedi azt, hogy függvény belsejében másik függvényt definiáljunk, és ebben az esetben a belső függvények látják a külső függvény lokális változóit is. Ennek részleteibe most nem megyünk bele (egy későbbi előadáson lesz róla szó), de a teljesség kedvéért itt most szerepel a gyorsrendezés ezt kihasználó megvalósítása:

def gyorsrendez(lista):
    def rendez(eleje, vege):
        vezer = lista[(eleje + vege) // 2]
        bal = eleje
        jobb = vege
        while bal <= jobb:
            while lista[bal] < vezer:
                bal += 1
            while lista[jobb] > vezer:
                jobb -= 1
            if bal <= jobb:
                tmp = lista[bal]
                lista[bal] = lista[jobb]
                lista[jobb] = tmp
                bal += 1
                jobb -= 1
        if eleje < jobb:
            rendez(eleje, jobb)
        if bal < vege:
            rendez(bal, vege)

    rendez(0, len(lista)-1)


lista = [9, 4, 7, 6, 8, 5, 3, 1, 2]
gyorsrendez(lista)
print(lista)

A fenti kód a gyorsrendezésnek csak egy variációja. Nem az igazi algoritmus, hanem egy olyan változat, amelyen keresztül könnyű megérteni a működést. Ugyanis nem igaz rá, hogy egy körben az aktuális vezérelem a helyére kerül. Arról van szó, hogy ha a vezérelem két oldalán keresett nála nagyobb, illetve kisebb elemek nem egyszerre fogynak el, akkor a vezérelem vándorolni kezd, és a bal, jobb mutatók csak az egyik oldalára kerülnek. Ezért pedig az aktuális vezérelem csak egy későbbi függvényhívásnál kerül helyre.

Ezt az okozza, hogy a szétválogatásban nem csak kékek és pirosak vannak, hanem van a vezérelem, a sárga is. Azt a sima kék-piros szétválogatásnál elvileg kéknek is és pirosnak is (vagy: kéknek sem és pirosnak sem) kellene tekinteni. Ideális esetben ide-oda pingpongozna a két ciklus a sárgával, úgy tudna az középen megérkezni.

Viszont ennek a megvalósítása nem triviális. Ehhez az kellene, hogy a csere után ne azt mondjuk, hogy bal += 1 és jobb -= 1, hanem kössük ezt if lista[bal] != vezer és if lista[jobb] != vezer feltételhez, hogy az ide-oda pingpongozás megvalósulhasson (egymás után kétszer is elmozdíthassuk ugyanazt az elemet). Ez viszont végtelen ciklust eredményezhetne akkor, ha a vezérelem olyan értékű, amiből kettő van.

Tehát a szétválogatás (particionálás) a fenti kódban nem tökéletes. De a gyorsrendezéshez elegendő, mert a szétválogatás által hagyott hibát a későbbi rendezési lépések kijavítják.