Gyorsrendezés

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 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.

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 Archiválva 2007. szeptember 30-i dátummal a Wayback Machine-ben. 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