# Gyorsrendezés (Quicksort) Üdvözöllek! Ez az anyag a Gyorsrendezés (Quicksort) algoritmus rejtelmeibe kalauzol el téged. A Gyorsrendezés az egyik leggyakrabban használt és leghatékonyabb rendezési algoritmus a számítástechnikában. Képzeld el, hogy egy hatalmas pakli kártyát kell sorba rendezned a legkisebbtől a legnagyobbig, de nincs sok időd! A Quicksort pontosan erre a problémára kínál elegáns és gyors megoldást. Tony Hoare fejlesztette ki 1959-ben, és 1961-ben publikálta. Az algoritmus az „osztás és meghódítás” (divide and conquer) elvén alapul, ami azt jelenti, hogy egy nagy problémát kisebb, könnyebben megoldható részproblémákra bont, majd ezek megoldásait kombinálja az eredeti probléma megoldásához. A Gyorsrendezés átlagos esetben rendkívül gyors, ezért széles körben alkalmazzák a számítástechnikában, például adatbázisok rendezésénél, operációs rendszerekben és egyéb alkalmazásokban, ahol nagy adathalmazokat kell hatékonyan sorba rendezni. Did you know that despite its name, Quicksort is not always the fastest sorting algorithm? In some specific scenarios, other algorithms like Mergesort or Heapsort can outperform it, especially when dealing with very specific data distributions or memory constraints. ### Az algoritmus működési elve A Gyorsrendezés alapvető stratégiája a következő lépésekből áll: 1. **Pivot kiválasztása:** A rendezendő listából kiválasztunk egy elemet, amelyet **pivotnak** nevezünk. Ennek az elemnek a megválasztása kulcsfontosságú az algoritmus hatékonysága szempontjából. A pivot fogja "osztani" a listát. 2. **Felosztás (Partitioning):** A lista többi elemét átrendezzük úgy, hogy a pivotnál kisebb elemek a pivot elé, a pivotnál nagyobb elemek pedig a pivot mögé kerüljenek. A pivot elem így a végső rendezett pozíciójába kerül. Ezt a lépést nevezzük felosztásnak. Ennek a lépésnek az a célja, hogy a pivot elem a végleges helyére kerüljön, és két, még rendezetlen al-lista jöjjön létre. 3. **Rekurzív rendezés:** A felosztás után két al-lista keletkezik: egy a pivotnál kisebb elemekből, egy pedig a pivotnál nagyobb elemekből. A Gyorsrendezés algoritmust rekurzívan alkalmazzuk mindkét al-listára, amíg azok egyetlen elemet nem tartalmaznak, vagy üresek nem lesznek (ezek már rendezettnek tekinthetők). Ez a folyamat addig ismétlődik, amíg az összes al-lista rendezetté nem válik, ami az egész eredeti lista rendezését eredményezi. > A **pivot** a Gyorsrendezés algoritmusban egy kiválasztott elem a rendezendő listából, amely referenciaként szolgál a felosztási (partitioning) fázisban, elválasztva a nála kisebb és nagyobb elemeket. ### Lomuto felosztási séma A felosztási lépésnek (partitioning) több implementációja is létezik, de az egyik leggyakrabban tanított és viszonylag egyszerűen érthető a **Lomuto felosztási séma**. Ez a séma feltételezi, hogy a pivot elem mindig a felosztandó tartomány utolsó eleme. (Más sémák, például a Hoare felosztás, hatékonyabbak lehetnek, de a Lomuto séma koncepcionálisan egyszerűbb.) A Lomuto felosztás lépései egy $A$ tömb $bal$ indextől $jobb$ indexig terjedő részére, ahol a pivot az $A[jobb]$ elem: 1. **Pivot kiválasztása:** Válasszuk ki a pivot elemet: $pivot = A[jobb]$. (A gyakorlatban a pivotot gyakran áthelyezik a $jobb$ pozícióba, ha máshonnan választották ki.) 2. **"Kisebb elemek" tartományának inicializálása:** Hozunk létre egy $i$ indexet, amely a „kisebb elemek” tartományának végét jelöli. Kezdetben $i = bal - 1$. 3. **Iteráció a többi elemen:** Iterálunk egy $j$ indexszel $bal$-tól $jobb - 1$-ig. 4. **Hasonlítás és csere:** Ha $A[j]$ kisebb vagy egyenlő, mint a $pivot$: a. Növeljük $i$-t eggyel ($i = i + 1$). b. Cseréljük fel $A[i]$ és $A[j]$ elemeket. Ezzel biztosítjuk, hogy az $i$ pozícióig minden elem kisebb vagy egyenlő legyen a pivotnál. 5. **Pivot elhelyezése:** Az iteráció befejezése után cseréljük fel $A[i + 1]$ és $A[jobb]$ (a pivot) elemeket. Ezzel a pivot a végső, rendezett pozíciójába kerül, és minden előtte lévő elem kisebb vagy eg