From Wikipedia, the free encyclopedia
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.
Gyorsrendezés | |
Kategória | rendezési algoritmus |
Adatstruktúra | tömb |
Legrosszabb időbonyolultság | |
Legjobb időbonyolultság | |
Átlagos idő bonyolultság | |
Legrosszabb tár bonyolultság |
A gyorsrendezés egy összehasonlító rendezés, és – hatékonyan implementálva – nem stabil rendezés.
A gyorsrendezést 1960-ban, az Elliott Brothers angol számítógépgyártónak dolgozva fejlesztette ki Hoare.[1]
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))
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.
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:
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.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.