Gyorsrendezés

A gyorsrendezés vagy quicksort algoritmus egy tömb elemeinek sorba rendezésére. Charles Antony Richard Hoare találmánya, egyike azon rendezéseknek, amiknek a bonyolultsága átlagos esetben $\Theta (n\log n)$. A gyorsrendezés általában gyorsabb az egyéb $\Theta (n\log n)$ rendezéseknél, mert a belső ciklusa a legtöbb architektúrán nagyon hatékonyan implementálható, és az adatok jellegének ismeretében az algoritmus egyes elemei megválaszthatóak úgy, hogy csak nagyon ritkán fusson négyzetes ideig.

Gyorsrendezés
Kategória	rendezési algoritmus
Adatstruktúra	tömb
Legrosszabb időbonyolultság	$O(n^{2})$
Legjobb időbonyolultság	$O(n\log n)$
Átlagos idő bonyolultság	$\Theta (n\log n)$
Legrosszabb tár bonyolultság	$O(n)$

Oszlopok magasság szerinti gyorsrendezése. A pirossal jelölt elem a támpont.

A gyorsrendezés egy összehasonlító rendezés, és – hatékonyan implementálva – nem stabil rendezés.

Története

A gyorsrendezést 1960-ban, az Elliott Brothers angol számítógépgyártónak dolgozva fejlesztette ki Hoare.

Működése

A gyorsrendezés oszd meg és uralkodj elven működik: a rendezendő számok listáját két részre bontja, majd ezeket a részeket rekurzívan, gyorsrendezéssel rendezi. A felbontáshoz kiválaszt egy támpontnak nevezett elemet (más néven pivot, főelem vagy vezérelem), és particionálja a listát: a támpontnál kisebb elemeket eléje, a nagyobbakat mögéje mozgatja. Teljes indukcióval könnyen belátható, hogy ez az algoritmus helyesen működik.

Az algoritmus pszeudokódja:

 function quicksort(array)
     var list less, equal, greater
     if length(array) ≤ 1  
         return array  
     select a pivot value pivot from array
     for each x in array
         if x < pivot then append x to less
         if x = pivot then append x to equal
         if x > pivot then append x to greater
     return concatenate(quicksort(less), equal, quicksort(greater))

Helyben rendező változat

Egy rövid lista helybeni rendezése. A keretes elem a támpont, a kék elemek nála kisebbek vagy egyenlőek, a pirosak pedig nagyobbak.

A fenti változat $\Omega (n)$ tárhelyet igényel, azaz annyit, amennyit az összefésüléses rendezés. A gyorsrendezés helyben is elvégezhető: az alábbi implementációban a partition eljárás az array tömb left és right közötti elemeit a pivotIndex elem két oldalára gyűjti:

  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left
     for i  from  left to right // left ≤ i < right
         if array[i] ≤ pivotValue 
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex

 function quicksort(array, left, right)
     if right > left
         select a pivot index (e.g. pivotIndex := left)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex-1)
         quicksort(array, pivotNewIndex+1, right)

A particionálás során a sorrend megváltozik, azaz ez már nem stabil rendezés.

Bonyolultsága

Ha minden particionálás felezné a listát, akkor a rekurziót egy $\log n$ mélységű fával lehetne ábrázolni, és mivel a fa minden szintjén összesen $n$ elem van (csak egyre több partícióban), az egyes szinteken a particionálásokhoz szükséges összes lépésszám $\Theta (n)$ lenne, azaz az algoritmus összesen $\Theta (n\log n)$ lépést igényelne. Ez általában is igaz, ha a nagyobb és a kisebb partíció aránya korlátos: ha például a kisebb partícióba mindig legalább az elemek 1%-a kerül, a fa még mindig legfeljebb $100\log n$ mély. A legrosszabb esetben azonban, ha az egyik lista mindig egyelemű, a fa lineáris lesz, és $n$ mélységű, azaz összesen $\sum _{i=0}^{n}\Theta (n-i)=\Theta (n^{2})$ lépés kell, vagyis a gyorsrendezés nem teljesít jobban, mint a beszúrásos vagy a kiválasztásos rendezés.

Ha a támpontot véletlenszerűen választjuk, akkor a várható bonyoultság mindig $\Theta (n\log n)$ lesz: minden lépésben 50% eséllyel választunk olyan támpontot, hogy a rövidebb listába legalább az elemek negyede kerül, és legfeljebb $2\log _{2}n$ ilyen vágás után eljutunk az egyelemű listáig, azaz a várható mélység $4\log _{2}n$. Az átlagos eset lényegében azonos ezzel: az elemek egy véletlen permutációján futtatni az algoritmust ugyanaz, mintha véletlenül választanánk.

Formálisabban, az összehasonlítások átlagos száma a következő rekurzív egyenlettel számítható:

$C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(n-i-1))=2n\ln n=1.39n\log _{2}n.$

ahol $n-1$ a támpont összehasonlítása a partíció összes tőle különböző elemével, az összeg másik tagja pedig a lehetséges particionálások átlaga. Ez azt jelenti, hogy a gyorsrendezés átlagosan csak körülbelül 39%-kal lassabb, mint legjobb esetben.

A levezetés részletesebben: ${\begin{aligned}C(n)&=(n-1)+C\cdot {\frac {n}{2}}+C\cdot {\frac {n}{2}}\\&=(n-1)+2C\cdot {\frac {n}{2}}\\&=(n-1)+2\left({\frac {n}{2}}-1+2C\cdot {\frac {n}{4}}\right)\\&=n+n+4C\cdot {\frac {n}{4}}-1-2\\&=n+n+n+8C\cdot {\frac {n}{8}}-1-2-4\\&=\cdots \\&=kn+2^{k}C\cdot {\frac {n}{2^{k}}}-(1+2+4+\cdots +2^{k-1}),{\mbox{ where }}\log _{2}n>k>0\\&=kn+2^{k}C\cdot {\frac {n}{2^{k}}}-2^{k}+1,\rightarrow n\log _{2}n+nC(1)-n+1.\end{aligned}}$

Gyors kiválasztás

A gyorsrendezés alapötlete kiválasztó algoritmusoknál is alkalmazható: ha egy lista k-adik legkisebb elemét kell kiválasztani, akkor a partíciók hosszából minden lépésben meg tudjuk mondani, melyikben van, tehát elég egyszeres rekurziót használni, amiből $\Theta (n)$ átlagos futásidő adódik. Az algoritmus módosításával a legrosszabb esetbeni $\Theta (n)$ idő is elérhető.

A $\Theta (n)$ lépésigényű kiválasztó algoritmust a gyorsrendezésben felhasználva választhatjuk minden lépésben a mediánt támpontnak, így a futásidő a legrosszabb esetben is $\Theta (n\log n)$ lesz. A gyakorlatban ezt ritkán használják, mert átlagosan valamivel lassabb.

Kapcsolat más rendezőalgoritmusokkal

A gyorsrendezés a rendezőfa egy speciális változatának is felfogható: ahelyett, hogy sorban beszúrnánk az elemeket egy fába, a rekurzív hívások adják a fastruktúrát.

A gyorsrendezés két fő vetélytársa a kupacrendezés és az összefésüléses rendezés. Mindkettő átlagos és legrosszabb esetben is $\Theta (n\log n)$ lépésigényű. Az összefésüléses rendezés stabil, és nagyon hatékony láncolt listákon és lassú elérésű tárban (például a merevlemezen) tárolt listákon, de tömbökön nagy a helyigénye. A kupacrendezésnek kisebb a helyigénye, mint a gyorsrendezésnek, de átlagban valamivel lassabb.

Irodalom

• Brian C. Dean, "A Simple Expected Running Time Analysis for Randomized 'Divide and Conquer' Algorithms." Discrete Applied Mathematics 154(1): 1-5. 2006.
• Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4(7), 321-322, 1961
• R. Sedgewick. Implementing quicksort programs, Comm. ACM, 21(10):847-857, 1978.
• David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 113–122 of section 5.2.2: Sorting by Exchanging.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 7: Quicksort, pp. 145–164.
• A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370–379.
• Faron Moller. Analysis of Quicksort. CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.
• Steven Skiena. Lecture 5 - quicksort. CSE 373/548 - Analysis of Algorithms. Department of Computer Science. State University of New York at Stony Brook.
• Conrado Martínez and Salvador Roura, Optimal sampling strategies in quicksort and quickselect. SIAM J. Computing 31(3):683-705, 2001.
• Jon L. Bentley and M. Douglas McIlroy, "Engineering a Sort Function, SOFTWARE---PRACTICE AND EXPERIENCE, VOL. 23(11), 1249—1265, 1993

További információk

• Gyorsrendezés különböző programnyelveken Archiválva 2008. május 9-i dátummal a Wayback Machine-ben a LiteratePrograms oldalon
• A gyorsrendezés szemléltetése külüllőmenti legényes tánccal

Kapcsolódó szócikkek

• Beszúrásos rendezés
• Flashsort