Rendezze az adatokat a tömb

Ebben a szakaszban kell tekinteni a híres algoritmus „” gyors „” válogatás, úgy, hogy a leggyorsabb körében speciális rendezési algoritmusok. Összehasonlításképpen, mi is úgy az egyik a rendezési algoritmusok, amelyek kisebb hatékonysággal, de sokkal egyszerűbb algoritmusok - behelyezés sort.

Válogató betétek

Beszúrási sort hasonló a folyamat csoszog a kártyákat a nevét. Hivatalvezető tesz minden név a kártyán, majd elrendezi a kártyákat betűrendben behelyezi a kártyát a verem tetején a megfelelő helyen. Nézzük ezt a folyamatot a mi példánkban listán ötszörös A = 50, 20, 40, 75, 35 (1. ábra).

A számítási hatékonyság válogató betétek

Válogató betétek igényel fix menetszám. Az n-1 elemek vannak behelyezve részeket az A [1], hogy az A [n-1]. Az i-edik lépésben a betét van termeltetve allista A [0] -A [i], és előírja, átlagos I / 2 összehasonlítás. Összehasonlítások összes száma megegyezik

Más módszerek, nem használja a rendezési betétek cseréjét. A komplexitás a algoritmus mérjük, és a összehasonlítások száma egyenlő O (N 2). A legjobb esetben - ha a forrás lista már rendezve. Ezután, az i-edik lépésben a betét keletkezik az A pont [i], és az összehasonlítások összes száma egyenlő az n-1, azaz a komplexitás O (n). A legrosszabb eset fordul elő, amikor a lista csökkenő sorrendben. Ezután minden beszúrási történik az A pontban [0] i és előírja összehasonlításokat. Az összehasonlítások összes száma egyenlő n (n-1) / 2, azaz a komplexitás O (n 2).

„Fast” válogatás

Tehát, megnéztük a tömb rendezési algoritmus komplexitása érdekében O (n2). Algoritmusok segítségével a fák (torna szortírozás, a keresési fa), jelentősen jobb teljesítményt O (n log2n). Annak ellenére, hogy szükség van egy másolata a tömb egy fa és vissza, ezeket a költségeket viseli a nagyobb hatékonyság válogatás is.

Széles körben használt kupacrendezés módszert is kezeli a tömb „in situ”, és van egy hatékonyságát O (n log2n). Azonban a „gyors” válogatás, amely találta K.Hoar, a legtöbb alkalmazás meghaladja kupacrendezés és a leggyorsabb ismert eddig.

Leírás A „gyors” válogatás

Mint a legtöbb rendezési algoritmusok, módszerek „gyors” az a fajta vett mindennapi tapasztalat. Rendezéséhez egy nagy halom ábécé kártyák név szerint, lehet osztani két kisebb csomagokra vonatkozóan néhány betű, mint például a K. nevű kisebb vagy egyenlő, mint a K, megy az egyik halom, és a másik - a másik.

Ezután minden halom ismét két részre oszlik. Például, a 2. ábra a partíció pontok a betűk F és R. A folyamat a felosztás kisebb és kisebb verem folytatódik.

Az algoritmus a „gyors” válogatás megosztási módszer milyen mértékben vonatkozik az a központi elem. Mivel mi nem engedhetjük meg, hogy dobjon egy köteg szórakoztató az asztal körül, mint az ábécé válogatás a kártyák, az elemek két csoportra oszthatók a tömb. Tekintsük algoritmus „gyors” válogatás például, majd megvitatják a technikai részleteket. Tegyük fel, hogy kapnak egy sor 10 egész:

szkennelés fázis

Eredetiség „gyors” válogatás úgy járunk két mutató a vizsgálat során listából. scanUp index feljebb a listán, és scanDown - lefelé. Ösztönözzük scanUp előremutató eleme [scanUp] nagyobb, mint a középső. Ezen a ponton, a beolvasás leáll, és készülünk az elemet talált a felső al-listán. Mielőtt ezt a mozgást fog történni, mi elősegítik Index scanDown le a listát, és megtalálja egy elem kisebb vagy egyenlő, mint a központi. Így van két elem, amelyek nem az al-listák, és lehet cserélni.

Ez a folyamat addig folytatódik, amíg scanUp és scanDown nem csökkenni fog egymás (scanUp = 6, scanDown = 5). Ezen a ponton úgy tűnik, scanDown allista melynek elemei kisebb vagy egyenlő, mint a központi. Megvan az a pont ketté a két lista, és megállapította, hogy a végleges álláspontját a központi elem. A mi példánkban cserélték számok 600 és 450, 800 és 350, 650 és 400 (lásd. 4. ábra).

Ezt követően az árfolyam értéke a központi elem A [0] A [scanDown]:

Ennek eredményeként, azt látjuk, két allista A [0] - A [5] és A [6] - A [9], ahol minden elemét az első allista egy második kevesebb elemet, és az utolsó elem az első allista van legnagyobb eleme. Így, akkor feltételezhetjük, hogy miután végzett aljegyzékét műveletek osztva elem A [5] = 550 (5. ábra). Ha most rendezni az al-lista minden egyedileg, akkor kapnánk teljesen rendezett tömböt. Vegyük észre, hogy valójában mindkét al-lista ugyanaz, mint az eredeti tömb, így lehetséges, hogy ugyanazt a algoritmust. Használja ugyanazt az algoritmust, hogy a részek tömb az úgynevezett rekurzív fázisban.

rekurzív fázis

Egy és ugyanazon eljárással, a két feldolgozott al-lista: Sl (A [0] - A [4]) és Sh (A [6] - A [9]). Elem nem kell kezelésére [5], mivel ez már a helyén.

Ugyanazt az algoritmust alkalmazzák mindegyik allista elosztjuk allistákra kisebb darabokra, míg a allista nem marad egyetlen elem, vagy amíg a allista üres.

algoritmus quicksort

Ez a rekurzív algoritmus osztja a lista [alacsony] - A [magas] a központi elem, amely ki van választva a közepén a lista

Cserét követően a központi tagja az A [alacsony], a kezdeti értékek indexekkel scanUp = alacsony + 1 és scanDown = nagy, jelezve, az elején és végén a lista, ill. Az algoritmus vezérli a két index. Először scanUp feljebb a listán, amíg összege scanDown vagy amíg egy nagyobb elem, mint a központ.

Miután elhelyezte scanUp scanDown index lefelé haladva a listán, amíg nem találkozik egy elem kisebb vagy egyenlő, mint a központi.

Az Exchange elem megszűnik, ha scanDown kisebb lesz, mint scanUp. Ezen a ponton azt jelzi, az elején scanDown bal allista, amely kevesebb vagy egyenlő, mint a központi elemek. scanDown index válik központi. Mark a központi eleme egy [alacsony]:

Kezelésére al-listák segítségével rekurzió. Észlelése után a szétosztási pont mi rekurzívan hívja quicksort paraméterek alacsony, közepes-1 és közép + 1, magas. megálló állapot akkor jelentkezik, ha a allista kevesebb mint két elem, mint egy szingli vagy egy üres tömböt nem kell szervezni.

A számítási bonyolultsága „gyors” válogatás

A teljes elemzés hatékonyságának „gyors” válogatás is elég nehéz. Jobb lenne megmutatni, hogy számítási komplexitás, számolás összehasonlítások számának valamilyen ideális feltételezéseket. Tegyük fel, hogy az n - ereje két, n = 2 k (k = log2 N), és a központi elem található, pontosan a közepén minden lista és felosztja két megközelítőleg egyenlő hosszúságú allista.

Az első szkennelési végezzük n-1 összehasonlítás. Ez létrehoz két allista mérete n / 2. A következő fázisban a feldolgozás egyes allista igényel kb n / 2 összehasonlítás. Az összehasonlítások összes száma ebben a fázisban egyenlő 2 (n / 2) = n. A következő fázis a négy aljegyzékét feldolgozása, amely előírja, 4 (N / 4) összehasonlítás, stb Végén a partíció folyamat után befejeztük k halad, amikor a kapott aljegyzékét tartalmazhatnak egy elemet. Összehasonlítások összes száma megegyezik egy körülbelül

A listát a teljes számítási komplexitás a forma „gyors” szortírozás O (N log2 N). Az ideális eset, hogy csak nézett, valójában akkor jelentkezik, ha a tömb már rendezve növekvő sorrendben. Ezután a központi eleme esik pontosan a közepén az egyes al-lista.

Ha a tömb rendezve csökkenő sorrendben, majd az első lépés a központi elem közepén található a listán, és cseréljük minden egyes eleme mind az első és a második allista. A kapott listája szortírozott szinte algoritmusnak van egy komplexitása érdekében O (N log2 N).

Legrosszabb esetben egy „gyors” válogatás lesz az egyik, ahol a központi eleme minden alkalommal esik allista Singleton, és minden más elem marad a második allista. Ez akkor fordul elő, amikor a központ mindig a legkisebb eleme. Tekintsünk egy szekvencia 3, 8, 1, 5, 9.

Az első lépésben készült n összehasonlítást, és több allista tartalmaz n-1 elemek. A következő lépés, ez a allista igényel n-1 és biztosítja összehasonlításokat allista n-2 elemek, stb A teljes száma összehasonlítások:

A legrosszabb bonyolultsága O (N 2), azaz a nem jobb, mint válogatás betétek és a választékot. Azonban ebben az esetben kóros, és nem valószínű a gyakorlatban. Általában az átlagos teljesítménye a „gyors” hasított magasabb megvizsgált minket mindenféle.

Quicksort algoritmus a kiválasztott alapján legsokoldalúbb válogatás eszközöket. Ha nem tudja megemészteni a legrosszabb teljesítmény érdekében kupacrendezés - stabilabb algoritmus, melynek bonyolultsága O (N log2 N) és csak attól függ a méret a listán.

Összehasonlítva tömbök rendezési algoritmusok

Általában Quicksort a leggyorsabb algoritmus. Mivel a hatékonyság egyenlő O (n log2n), ez egyértelműen jobb bármely algoritmus sorrendben O (n 2). Ítélve az eredmények a felsorolt ​​vizsgálatokat az alábbi táblázatban, az is gyorsabb, mint bármely rendezési sorrendjét O (N log2 N), már tárgyalt az utolsó kérdés. Felhívjuk figyelmét, hogy a hatékonysága a „gyors” szortírozás O (N log2 N) még szélsőséges esetekben. De rendezés a keresési fa ezekben az esetekben válik O (n 2) komplexet, kialakítva a fa degenerált.

Rendezés fa

Ábra8 összehasonlítása rendezési sorrendje O (n log2n)

összehasonlítása a fajta

Ez a program végez összehasonlítást rendezési algoritmusok, a bemutatott adatok 7. és 8. ábra Itt bemutatunk csak az alapvető szerkezetét a program. Timing TickCount végre egy függvényt, amely visszaadja a száma 1/60 másodperc törtrésze óta eltelt az a program indítását.