A válogatás algoritmusa
A rendezési algoritmus egy algoritmus a listák elemeinek megrendeléséhez. Abban az esetben, ha a listaelemnek több mezője van, akkor a rendkritériumként szolgáló mezőt rendező kulcsnak nevezik. A gyakorlatban a kulcs gyakran egy szám, és a többi mezőben az algoritmus működését nem befolyásoló adatok tárolódnak.
A probléma megfogalmazása
,
Feltételezzük, hogy minden egyes elemnél (a másolással nem járó egyéb információ mellett) egy kulcs is társul. A gombok készletén egy lineáris (vagy tökéletes) sorrend sorrendje van. amelyekre az alábbi feltételek teljesülnének:
a trichotomia törvénye. bármelyik számára, vagy, vagy;
tranzitivitás. minden esetben, ha és akkor.
A nem-kiválással történő szortírozás feladata olyan elemek permutációjának megtalálása, amelyeknek indikátorai vannak, amelyeknél a kulcsok a meg nem haladó sorrendben vannak elrendezve:
Az algoritmus és a permutáció használatának eredményeképpen megkapjuk a rendezett tömböt:
Hasonlóképpen, a rendezés nem növelhető.
A rendezési algoritmus értékelése
A rendezés algoritmusait a végrehajtás sebessége és a memóriahasználat hatékonysága alapján becsülik meg:
Az idő a fő paraméter, amely az algoritmus sebességét jellemzi. Úgy is nevezik számítási komplexitásnak. A megrendeléshez a legrosszabb a fontos. szekunder és jobb viselkedést az algoritmus szempontjából több bemeneti teljesítmény A. Ha a algoritmust alkalmazunk, hogy a bemeneti A halmaz jelölik n = | A |. Egy tipikus jó viselkedést az algoritmus - O (n log n) és a rossz viselkedés - O (n 2). A megrendelés ideális viselkedése O (n). Az algoritmusok szétválogatása csak absztrakt kulcs összehasonlító művelettel mindig legalább Ω (n log n) összehasonlítást igényel. Mindazonáltal Khan rendezési algoritmus (Yijie Han) a számítási komplexitás O (n log log n log log log n), kihasználva azt a tényt, hogy a kulcs a hely korlátozott (rendkívül nehéz, és O -oboznacheniem nagyon magas rejtőzködő faktor ami lehetetlenné teszi azt a mindennapi gyakorlatban). Van még a hálózatok válogatásának fogalma is. Feltételezve, hogy lehetőség van egy időben (például, egy párhuzamos számítási) elvégzésére számos összehasonlításokat számok sorrendje N O (log 2 n) műveleteket. Az n szám kell előre ismert;
Memória - Számos algoritmusra van szükség további memória elosztására az adatok ideiglenes tárolásához. Ezek az algoritmusok általában O (log n) memóriát igényelnek. A becslés nem veszi figyelembe az eredeti tömb által elfoglalt helyet és a bemeneti sorrendtől független költségeket, például a programkód tárolásához (mivel mindez O (1) -ot fogyaszt). Az olyan algoritmusok kiválasztása, amelyek nem fogyasztanak további memóriát, a helyszínen történő rendezésre utalnak.
Tulajdonságok és osztályozás
Stabilitás (stabil stabilitás) - a stabil válogatás nem változtatja meg az azonos kulcsokkal rendelkező elemek relatív helyzetét [3].
A viselkedés természetessége a módszer hatékonysága a már megrendelt vagy részlegesen rendezett adatok feldolgozása során. Az algoritmus természetesen viselkedik, ha figyelembe veszi a bemeneti sorozatot és jobban működik.
Az összehasonlítási művelet használata. Az algoritmusok, amelyek az elemek egymás közötti összehasonlítását a válogatáshoz használják, összehasonlítás alapján hívják. Az algoritmusok legrosszabb esetének minimális összetettsége O (n log n), de alkalmazásukban rugalmasak. Speciális esetekben (adattípusok) hatékonyabb algoritmusok vannak.
Az algoritmus másik fontos tulajdonsága annak hatóköre. Itt a megrendelés fő típusai kétek:
A belső rendezés olyan tömbökkel működik, amelyek teljes mértékben RAM-ban véletlenszerű hozzáféréssel rendelkeznek minden cellához. Az adatok általában ugyanazon a helyen kerülnek elhelyezésre, további költségek nélkül.
A modern személyi számítógépes architektúrákban a paging és a memória gyorsítótár széles körben használatos. A rendezési algoritmust jól össze kell kapcsolni az alkalmazott gyorsítótár- és swap algoritmusokkal.
A külső válogatás tömeges tárolóeszközökkel működik, de nem véletlenszerű hozzáféréssel, hanem egymás után (fájlrendelés), azaz csak egy elem látható egy adott pillanatban, és a visszatekerés költségei a memóriához képest indokolatlanul nagyok. Ez további korlátozásokat ír elő az algoritmusra, és speciális rendelési módokhoz vezet, általában további lemezterületet használva. Ezenkívül a külső memóriában lévő adatokhoz való hozzáférés sokkal lassabb, mint a RAM műveletek.
A közeghez való hozzáférés szekvenciálisan történik: bármely pillanatban csak az aktuálisat követő elem olvasható vagy írható.
Az adatok mennyisége nem teszi lehetővé a RAM-ban való elhelyezkedést.
Az algoritmusokat is osztályozzák:
a további memória szükségessége vagy hiánya
az adatszerkezet ismeretének szükségessége az összehasonlítási művelet körén kívül esik, vagy hiánya
Rendezési algoritmusok listája
Ebben a táblázatban n az elrendezendő rekordok száma, és k az egyedi kulcsok száma.
Stabil válogatás algoritmusai
Kiválasztási sorrend - Az algoritmus összetettsége: O (n 2); Keressétek a legkisebb vagy legnagyobb elemet, és helyezzük el egy rendezett lista elejére vagy végére
Válogatás buborékkal (English.Bubblesort) - az algoritmus összetettsége: O (n2); Mindegyik indexpárnál kicserélődik, ha az elemek nem rendezettek.
Keverés szerinti osztályozás (Shaker, Koktél rendezés, kétirányú buborékfajta) - Az algoritmus komplexitása: O (n 2)
A törpe szortírozás - közös a buborék válogatásával és a betétek rendezésével. Az algoritmus összetettsége O (n2).
Insertion sort - Az algoritmus komplexitása: O (n 2); Határozza meg, hogy az aktuális elem hol legyen a rendezett listában, és tegye be ott
Merge sort - Az algoritmus összetettsége: O (n log n); O (n) kiegészítő memória szükséges; A lista első és második felét külön állítjuk össze, majd egyesítjük a rendezett listákat
Rendezés egy bináris fával (English.Treesort) - Az algoritmus komplexitása: O (n log n); O (n) kiegészítő memóriát igényel
Algoritmus elrendezése Timsort (English.Timsort) - Az algoritmus komplexitása: O (n log n); O (n) kiegészítő memória szükséges; Kombinált algoritmus (betétrendezés és összefésülés szortírozással, Python használatára fejlesztve [
Counting sort - Az algoritmus komplexitása: O (n + k); O (n + k) további memória szükséges (3 variáns figyelembe vehető)
Blokk sorrendje (Bucket sort) - Az algoritmus összetettsége: O (n); Szükség van O (k) további memóriára és a rendezett adatok természetére vonatkozó ismeretekre, amelyek túlmutatnak a "átrendezés" és a "összehasonlítás" funkciókon.
Ellenállhatatlan rendezési algoritmusok
Kiválasztási sorrend - Az algoritmus összetettsége: O (n 2); Keressétek a legkisebb vagy legnagyobb elemet, és helyezzük el egy rendezett lista elejére vagy végére
Shell sort - Az algoritmus komplexitása: O (n log 2 n); próbálja javítani a betét válogatását
Comb sort - Az algoritmus összetettsége: O (n log n)
Piramisrendezés (Heap Sort, Heapsort) - Az algoritmus komplexitása: O (n log n); kapcsolja be a listát egy kupacba. vegye a legnagyobb elemet, és add hozzá a lista végéhez
Smoothsort - Az algoritmus összetettsége: O (n log n)
Gyors válogatás (Quicksort), egy változatban, minimális memória költségekkel - Az algoritmus komplexitása: O (n log n) - az átlagos idő, O (n 2) - a legrosszabb esetben; köztudottan a leggyorsabban ismert a nagy véletlen listák megrendelésére; az eredeti adatkészlet két részének felosztásával úgy, hogy az első fél bármely eleme a második fél bármely eleméhez képest rendezve legyen; akkor az algoritmust rekurzívan alkalmazzák minden félre. O (n) kiegészítő memória használata esetén a rendezés stabil.
Introsort - Az algoritmus komplexitása: O (n log n), gyors és piramisos válogatás kombinációja. A piramis rendezést akkor használjuk, ha a rekurzió mélysége meghaladja a log (n) értéket.
Táblázat válogatás: O (n log n) - legrosszabb esetben O (n) memóriát igényel, továbbá megtalálja a leghosszabb növekedési utóbbit
A Stooge rendezés egy rekurzív rendezési algoritmus, amelynek időbeli összetettsége van.
Bitsebesség szerinti szortírozás - Az algoritmus komplexitása: O (n · k); O (k) további memória szükséges.
A digitális válogatás ugyanaz, mint a Bitwise rendezés.
Gyakorlati rendezési algoritmusok
Bogosort - O (n · n!) Átlagosan. Arbitrálisan keverje össze a tömböt, ellenőrizze a sorrendet.
Rendezés permutációval - O (n · n!) - a legrosszabb idő. Minden pár esetében a helyes sorrendet ellenőrzik, és az eredeti tömb minden lehetséges permutációját generálják.
Hülye fajta - O (n3); A rekurzív verzióhoz O (n2) kiegészítő memória szükséges
Bead Sort - O (n) vagy O (√n), speciális hardvert igényel
A palacsinta válogatása - O (n), speciális hardvert igényel
Az összehasonlításon alapuló algoritmusok
Blokk sorrend (Bucket sort)
Lexicográfiai vagy bitrendszerű (Radix sort)
Sorszámozás
Más rendezési algoritmusok