Felfedező vagy feltaláló | Charles Antony Richard Hoare |
---|---|
A felfedezés dátuma | 1961 |
Kapcsolódó kérdések | Rendezés összehasonlítás alapján ( in ) , felosztás és meghódítás , rendezési algoritmus |
Adatszerkezet | lista vagy táblázat |
Legrosszabb esetben | , |
---|---|
Átlagos | |
Legjobb eset |
Legrosszabb esetben | |
---|---|
Átlagos |
Az IT , a gyors rendezés , vagy válogatás hub (angol quicksort ) egy válogatás algoritmus által feltalált CAR Hoare a 1961 és tervei alapján eljárás az oszd meg és uralkodj . Általában táblákon használják , de listákhoz is adaptálható . Tömbök esetében ez egyfajta helyben van, de nem stabil .
Az átlagos komplexitás a gyors rendezés az n tételek arányos n log n , amely optimális összehasonlítás sort, de a legrosszabb esetben komplexitás négyzetes. Ezen elméleti hátrány ellenére a gyakorlatban az egyik leggyorsabb fajta, ezért az egyik leggyakrabban használt. A legrosszabb eset valószínûtlen, ha az algoritmust helyesen hajtják végre, és az Introsort variánssal végérvényesen elkerülhetõ .
A gyors rendezés azonban nem tudja kihasználni azt a tényt, hogy a bejegyzés már majdnem rendezve van. Ebben a konkrét esetben előnyösebb az insert sort vagy a smoothsort algoritmus használata .
A Quicksortot 1960-ban Tony Hoare , a Moszkvai Állami Egyetem akkori vendéghallgatója hozta létre a Nemzeti Fizikai Laboratórium gépi fordításának tanulmánya során . Ezután szüksége van az algoritmusra a lefordítandó szavak rendezésére annak érdekében, hogy azok megfeleljenek egy már létező orosz-angol szótárnak, amelyet mágnesszalagon tárolnak .
- Lazán QUICKSORT néven írtam az eljárást, amelyre számítástechnikus karrierem épült. Kétségtelen, hogy ezt az Algol 60 tervezőinek zsenialitásának kell tulajdonítani, akik a rekurziót beépítették nyelvükbe, és lehetővé tették, hogy ilyen elegánsan leírjam találmányomat a világ számára. A programozási nyelvek egyik elsődleges céljának tartom a jó ötletek elegáns kifejezésének lehetővé tételét. " CAR Hoare, „ A császár régi ruhái ” , az ACM közleményei , vol. 24, n o 21981. február, P. 5–83 ( DOI 10.1145 / 358549.358561 , online olvasás [PDF] )A módszer abból áll, hogy a tömb egy elemét (ún. Pivot) helyezzük a végére, az összes elemet felcseréljük úgy, hogy mindazok, amelyek kisebbek a forgásnál, balra kerüljenek, és mindazok, amelyek nagyobbak, mint a forgás, a jobb.
Ezt a műveletet partíciónak nevezzük. Az egyes altáblákhoz meghatározunk egy új pivot-t, és megismételjük a particionálási műveletet. Ezt a folyamatot rekurzívan ismételjük, amíg az összes elem rendeződik.
Konkrétan egy altömb particionálása:
Az [első, utolsó] intervallumban véletlenszerűen kiválasztott pivot garantálja az algoritmus hatékonyságát, de vannak más lehetőségek is (lásd „ A forgás és bonyolultság megválasztása ” című részt).
A particionálás lineáris időben, a helyén végezhető. A legegyszerűbb megvalósítás az első és az utolsó elem tömbjének iterálása, a menet közben a partíció kialakítása: Az alábbi algoritmus i- edik lépésében az elemek kisebbek, mint a forgás, míg nagyobbak, mint a forgás .
Ez a particionáló algoritmus instabillá teszi a gyors rendezést : nem feltétlenül őrzi meg az azonos rendezési kulccsal rendelkező elemek sorrendjét. Megoldhatjuk ezt a problémát úgy, hogy minden elemhez hozzáadjuk a kiindulási helyzetre vonatkozó információkat, és hozzáadunk egy tesztet a helyzethez, ha a rendezési kulcs egyenlő.
A particionálás akkor jelenthet problémát, ha a tömb elemei nem különböznek egymástól. A leginkább degenerált esetben, azaz egyenlő elemek tömbjében az algoritmus ezen verziója másodfokú bonyolultsággal rendelkezik. Számos megoldás lehetséges: például csökkenteni a különálló elemek esetére a leírt módszerrel a rendezés stabilá tételéhez, vagy más algoritmust használni (lásd az „ Alternatív particionáló algoritmus ” részt).
A forgáspont kiválasztásának egyszerű módja, ha mindig az aktuális részrajz első elemét veszi (vagy az utolsó). Ha a bejegyzések minden lehetséges permutációja egyformán valószínű , akkor a pivot ilyen módon történő kiválasztásával a quicksort átlagos bonyolultsága Θ ( n log n ). A legrosszabb eset bonyolultsága azonban Θ ( n 2 ), és ez akkor érhető el, amikor a bejegyzés már rendezve vagy majdnem rendezve van.
Ha a táblázat közepét tekercsnek vesszük, az eredmény ugyanaz, bár a problematikus bejegyzések eltérnek.
Lehetséges véletlenszerű permutációt alkalmazni a táblára annak elkerülése érdekében, hogy az algoritmus szisztematikusan lassuljon bizonyos bemeneteken. Ez a technika azonban általában kevésbé hatékony, mint a forgás véletlenszerű kiválasztása.
Ha az algoritmus leírásában megadott módszert alkalmazzuk, vagyis az összes elem közül véletlenszerűen egyenletesen választjuk a forgatást , akkor a gyors rendezés átlagos komplexitása ' ( n log n ) n' bármely bejegyzésnél. A legrosszabb esetben a komplexitás Θ ( n 2 ). A komplexitás szórása azonban csak Θ ( n ), ami azt jelenti, hogy az algoritmus alig tér el az átlagos végrehajtási időtől.
A legjobb esetben az algoritmus Θ ( n log n ) -ban van.
A komplexitás kiszámításaBizonyítékot adunk a mérettömb gyors válogatásának átlagos időbeli összetettségéről .
Megjegyezzük a táblázat növekvő sorrendben megadott elemeit. Mert megjegyezzük . Kezdetben a rendezendő tömb az, ahol az egész számok permutációja 1 és között van .
Az elvégzendő műveletek a pivot-választások és az egyes pivot körüli partíciók során végrehajtott összehasonlítások. Amint kiválasztják a forgást, az már nem vesz részt a következő partíciókban, ezért az algoritmus végrehajtása legfeljebb a forgatás választását jelenti, és mindegyik választás állandó időben történik. Ezenkívül bármely elemet legfeljebb egyszer hasonlítanak össze egy elemhez, mert bármely elemet csak egy pivot-hoz hasonlítanak, és ha a partíció egy adott pivot körül van végrehajtva, ez már nem avatkozik be az algoritmus végrehajtásába, ha a partíció befejeződött. Az összehasonlítás teljes számának figyelembevételével azt kapjuk, hogy a végrehajtás összetettsége tehát igen . Sőt, ha megjegyezzük azt a véletlen változót, amely 1-et ér, ha összehasonlítjuk vele, és 0-val, ha nem, akkor arra következtetünk, hogy van egy adott végrehajtáshoz . Igyekszünk számítani az elvárás az . Ez azt jelenti .
Vagy akkor és csak akkor hasonlítják össze, ha a forgáspontként választandó első elem vagy . Valóban, ha az egy másik elem, amely a következők közül választott első a tengelyre, majd és küldik két különböző al-tömbök a pontszámot, valamint az összehasonlításokat az kizárólag között elemét azonos al-tömb. Ráadásul annak a valószínűsége, hogy az első elem , amelyet pivotnak kell választani, azért érdemes vagy érdemes, mert a pivot választása egyenértékű és kölcsönösen kizárja, és mert elemeket tartalmaz .
Így van .
Arany (ez a harmonikus sorozat tulajdonsága ).
Ezért .
Tehát a quicksort átlagos bonyolultsága, amikor a forgatást véletlenszerűen választják meg, az .
Elméletileg az algoritmus bonyolultságát a legrosszabb esetben Θ ( n log n ) értékre tehetjük, ha forgatásként az altömb medián értékét vesszük . Sőt, ebben az esetben a fa a rekurzív hívások az algoritmus magassága azonos , és minden egyes szakaszában az a komplexitás . A BFPRT vagy a medián medián algoritmus lehetővé teszi ennek a mediánnak a determinisztikus módon történő kiszámítását lineáris időben.
De az algoritmus a gyakorlatban nem elég hatékony, és ezt a változatot kevesen használják.
Van egy összetettebb particionáló algoritmus, amely csökkenti a particionálás során végrehajtott cserék számát. Ezenkívül az elfordulással egyenlő elemek jobban eloszlanak az utóbbi két oldalán, mint az előző algoritmusnál. Így az algoritmus Θ-ben ( n log n ) megmarad még egy tömbön is, amelynek minden eleme azonos.
Az algoritmus alapelve a következő:
Formalizálni lehet ezt az algoritmust úgy, hogy lineáris legyen:
partitionner(tableau T, premier, dernier, pivot) échanger T[pivot] et T[premier] i = premier + 1, j = dernier tant que i < j tant que i < j et T[i] < T[premier], faire i := i + 1 tant que i < j et T[j] > T[premier], faire j := j - 1 échanger T[i] et T[j] i := i + 1, j := j - 1 fin tant que ''// le tableau est à présent en 3 parties consécutives : pivot, partie gauche, partie droite'' ''// dans partie gauche, tous les éléments sont <= pivot'' ''// dans partie droite, tous les éléments sont >= pivot'' ''// mais les deux parties peuvent se chevaucher : i-j peut être 0, 1 ou 2'' ''// il faut replacer le pivot entre les 2 parties et retourner l'indice du pivot : c'est assez compliqué...'' ''// il vaut mieux laisser le pivot à sa place au départ et le déplacer en cas de chevauchement :''Hasznos optimalizálás az algoritmus megváltoztatása, amikor a válogatatlan adathalmaz kicsi lesz. Az allisták optimális mérete a használt hardvertől és szoftvertől függ, de 15 elem nagyságrendű. Ezután használhatja a válogatás szerinti rendezést vagy a beszúrás szerinti rendezést . A kiválasztási sorrend biztosan nem lesz hatékony sok adat esetében, de nagyobb egyszerűsége miatt gyakran gyorsabb, mint a rövid listákon lévő gyorsválogatás.
Robert Sedgewick fejlesztést javasol (Sedgesort néven), amikor egyszerűsített rendezést használ a kis allistákhoz: csökkenthető a szükséges műveletek száma, ha a gyors rendezés befejezése után elhalasztjuk a kis allisták rendezését , amely után beillesztési rendezést hajtunk végre a teljes tömb.
LaMarca és Ladner megvizsgálták „a gyorsítótárak hatását a rendezés teljesítményére”. Ez fontos kérdés a közelmúltbeli architektúrákban, amelyek gyors késleltetési idejű gyorsítótár- hierarchiákkal rendelkeznek, amikor az adat-gyorsítótár nem működik. Arra a következtetésre jutottak, hogy bár Sedgewick optimalizálása csökkenti a végrehajtott utasítások számát, a gyorsítótárak sikerességi aránya is csökken a memória-hozzáférések szélesebb körű szétszórtsága miatt (amikor a beszúrási sort az egész asztal végén végzik, és nem úgy, ahogy megy), ami a válogatási teljesítmény romlásához vezet. A hatás azonban nem drámai, és csak akkor válik jelentősebbé, ha több mint 4 millió 64 bites elemet tartalmazó tömbök vannak. Ezt a tanulmányt Musser idézi.
IntrosortA gyors válogatás egyik változata, amely széles körben elterjedt introsort aka introspektív rendezés . Gyors rendezéssel kezdődik, majd halom rendezést használ, ha a rekurziós mélység meghalad egy bizonyos előre meghatározott határt. Így a legrosszabb komplexitása Θ ( n log n ).
A quicksort naiv megvalósítása a legrosszabb esetben a tömb méretével arányos memóriaterületet használ . A memória mennyiségét minden esetben Θ-re (log n ) korlátozhatjuk, ha az első rekurzív hívást a legkisebb listán hajtjuk végre. A második rekurzív hívás, amely az eljárás végén található, terminál rekurzív . Ezért iterációvá alakítható a következőképpen:
tri_rapide(T, gauche, droite) tant que droite-gauche+1 > 1 sélectionner un pivot T[pivotIndex] pivotNewIndex := partition(T, gauche, droit, pivotIndex) si pivotNewIndex-1 - gauche < droit - (pivotNewIndex+1) tri_rapide(T, gauche, pivotNewIndex-1) gauche := pivotNewIndex+1 sinon tri_rapide(T, pivotNewIndex+1, droit) droit := pivotNewIndex-1 fin_si fin_tant_queA Quickselect nevű gyors válogatás ihlette algoritmus , amely átlagosan lineáris időben működik, lehetővé teszi egy tömb k- edik legkisebb elemének meghatározását . Figyelemre méltó egyedi eset a k = n / 2, amely megfelel a medián keresésének .
A Quickselect algoritmus alapelve a következő: minden lépésben egy véletlenszerűen kiválasztott forgatókönyv szerint hajtunk végre egy partíciót. Miután elkészült a partíció, meg lehet tudni, hogy a partíció melyik oldalán található a k- edik elem (vagy ha ez maga a csukló). Ha a pivot nem a k- edik elem, rekurzív módon hívjuk meg az algoritmust, de csak azon az oldalon, ahol az elem található. Az algoritmus végén a tömb k- edik eleme a tömb k- edik legkisebb eleme.