Gyorsrendezés

A Wikipédiából, a szabad enciklopédiából
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. C. A. R. 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[szerkesztés | forrásszöveg szerkesztése]

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

Működése[szerkesztés | forrásszöveg szerkeszté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[szerkesztés | forrásszöveg szerkesztése]

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 nagyobbak vagy egyenlőek.

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[szerkesztés | forrásszöveg szerkesztése]

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 partcí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{align}
 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^kC \cdot \frac{n}{2^k} - (1 + 2 + 4 + \cdots + 2^{k-1}), \mbox{ where } \log_2 n > k > 0\\
      &= kn + 2^kC \cdot \frac{n}{2^k} - 2^k + 1,
      \rightarrow n \log_2 n + nC(1) - n + 1.
\end{align}

Gyors kiválasztás[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

  • 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

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  1. Timeline of Computer History: 1960. Computer History Museum

További információk[szerkesztés | forrásszöveg szerkesztése]

Lásd még[szerkesztés | forrásszöveg szerkesztése]