frame|right|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 . A gyorsrendezés általában gyorsabb az egyéb 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 right|200px|thumb|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 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 mélységű fával lehetne ábrázolni, és mivel a fa minden szintjén összesen elem van (csak egyre több partícióban), az egyes szinteken a particionálásokhoz szükséges összes lépésszám lenne, azaz az algoritmus összesen 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 mély. A legrosszabb esetben azonban, ha az egyik lista mindig egyelemű, a fa lineáris lesz, és mélységű, azaz összesen 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 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 ilyen vágás után eljutunk az egyelemű listáig, azaz a várható mélység . 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ó:

ahol 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:

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 átlagos futásidő adódik. Az algoritmus módosításával a legrosszabb esetbeni idő is elérhető.

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

Források

További információk Gyorsrendezés különböző programnyelveken 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

Kategória:Rendezési algoritmusok

no:Sorteringsalgoritme#Quick sort