Mind a rendezési technikák, mind a gyors rendezés és egyesítés a felosztási és meghódítási módszerre épül, amelyben az elemek halmaza elválik, majd az átrendeződés után egyesül. A gyors rendezés általában több összehasonlítást igényel, mint az egyesítés sorrendje egy nagy elemcsoport rendezéséhez.
Összehasonlító táblázat
| Az összehasonlítás alapja | Gyors rendezés | Egyesítés |
|---|---|---|
| A tömb elemeinek megosztása | Az elemek listájának felosztása nem feltétlenül felét oszlik meg. | A tömb mindig felére van osztva (n / 2). |
| A legrosszabb bonyolultság | O (n2) | O (n log n) |
| Jól működik | Kisebb tömb | Jól működik bármilyen típusú tömbben. |
| Sebesség | Gyorsabb, mint a többi adatgyűjtési algoritmus. | Következetes sebesség minden típusú adatkészletben. |
| További tárolási helyigény | Kevésbé | Több |
| Hatékonyság | A nagyobb tömbök esetében nem hatékony. | Hatékonyabb. |
| Rendezési módszer | Belső | Külső |
A gyors rendezés meghatározása
A gyors rendezést széles körben használják a válogató algoritmus, mivel a rövid tömbök számára gyors. Az elemek halmaza ismételten részekre van osztva, amíg nem lehetséges tovább osztani. A gyors rendezést partíciócserének is nevezik. Kulcselemet használ (az úgynevezett pivot) az elemek elválasztásához. Az egyik partíció olyan elemeket tartalmaz, amelyek kisebbek, mint a kulcselem. Egy másik partíció olyan elemeket tartalmaz, amelyek nagyobbak, mint a kulcselem. Az elemeket rekurzív módon rendezik.
Tegyük fel, hogy A egy A [1], A [2], A [3], …… .., A [n] n szám, amelyet rendezni kell. A gyors rendezési algoritmus a következő lépésekből áll.
- Az első elem vagy a véletlenszerű elem, amely kulcsként van kiválasztva, az = A (1) kulcsot veszi fel.
- Az „alacsony” mutató a második és az „up” mutató a tömb utolsó elemére kerül, azaz alacsony = 2 és fel = n;
- Következetesen növelje az „alacsony” mutatót egy pozícióig, amíg (A [alacsony]> gomb).
- Folyamatosan csökkentse az „up” mutatót egy pozícióval, amíg (A [fel] <= gomb).
- Ha a felfelé nagyobb az A [alacsony] csomópont A [felfelé].
- Ismételje meg a 3.4. És 5. lépést, amíg az 5. lépésben bekövetkezett állapot meghibásodik (azaz <<alacsony), majd az A [fel] felcserélése a billentyűvel.
- Ha a kulcsból balra eső elemek kisebbek, mint a kulcs, és a kulcs jobb oldali elemei nagyobbak, mint a kulcs, akkor a tömböt két részcsoportba osztjuk.
- A fenti eljárást ismételten alkalmazzák az alegységekre, amíg a teljes tömböt nem rendezik.
Előnyök és hátrányok
Jó átlagos eset viselkedése van. A gyors rendezés futási idejének összetettsége jó, azaz gyorsabb, mint az algoritmusok, mint például a buborékfajta, a beillesztés és a kiválasztás rendezése. Ez azonban összetett és nagyon rekurzív, ezért nem alkalmas nagy tömbökre.
Az egyesítés rendezésének meghatározása
Az egyesítés egy külső algoritmus, amely szintén az osztás és a meghódítás stratégián alapul. Az elemeket újra és újra al-tömbökre osztják (n / 2), amíg csak egy elem marad meg, ami jelentősen csökkenti a rendezési időt. A kiegészítő tömböt a kiegészítő tömb tárolására használja. Az egyesítés sorrendje három tömböt használ, ahol kettőt használnak minden fél tárolására, a harmadik pedig a végleges sorrendű lista tárolására szolgál. Minden egyes tömböt rekurzívan rendezünk. Végül az alcsoportok egyesülnek, hogy a tömb n elemmérete legyen. A lista mindig csak félig (n / 2) különbözik a gyors rendezéshez.
Legyen A az a sorrend, amely az A [1], A [2], ………, A [n] osztályozandó elemek számát tartalmazza. Az egyesítési sorrend az adott lépéseket követi.
- Osztjuk el az A tömböt körülbelül n / 2 rendezett alcsoportra 2-vel, ami azt jelenti, hogy az (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]) (A [n-1], A [n]) alrendszerek rendezett sorrendben kell lenniük.
- Az egyes párpárokat egyesítjük, hogy megkapjuk a 4-es méretű válogatott alrészek listáját; az alkategóriák elemei rendezett sorrendben is vannak (A [1], A [2], A [3], A [4]), ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……, (A [n-3], A [n-2], A [n-1], A [n]).
- A 2. lépést ismételten hajtjuk végre mindaddig, amíg csak egy n méretű méretezett tömb van.
Előnyök és hátrányok
Az egyesítés rendezési algoritmus pontosan ugyanolyan és pontos módon működik, függetlenül a rendezésben részt vevő elemek számától. A nagy adatkészlet esetén is jól működik. Azonban a memória nagyobb részét fogyasztja.
A gyors rendezés és az egyesítés rendezési különbségei
- Az egyesítési sorrendben a tömböt csak két félre kell osztani (azaz n / 2). Gyors rendezésben nincs kényszer arra, hogy a listát egyenlő elemekre lehessen osztani.
- A gyors rendezés legrosszabb összetettsége O (n2), mivel sokkal több összehasonlítást igényel a legrosszabb állapotban. Ezzel ellentétben az egyesítési rend ugyanazzal a legrosszabb esettel és az átlagos esettanulmányokkal rendelkezik, azaz O (n log n).
- Az egyesítés a jól használható bármilyen típusú adatkészleten, függetlenül attól, hogy nagy vagy kicsi. Éppen ellenkezőleg, a gyors rendezés nem működik jól nagy adatállományokkal.
- A gyors rendezés gyorsabb, mint az egyesítés, egyes esetekben, például kis adatállományok esetében.
- A válogatás rendezése további memóriát igényel a kiegészítő tömbök tárolásához. Másrészt, a gyors rendezés nem igényel sok helyet a további tároláshoz.
- Az egyesítés rendszere hatékonyabb, mint a gyors rendezés.
- A gyors rendezés a belső rendezési módszer, ahol a rendezendő adatokat egy időben a fő memóriában állítják be. Ezzel ellentétben az egyesítés rendezése olyan külső válogatási módszer, amelyben a rendezendő adatokat egyidejűleg nem lehet a memóriában elhelyezni, és néhányat a kiegészítő memóriában kell tartani.
Következtetés
A gyors rendezés gyorsabb esetek, de bizonyos helyzetekben nem hatékony, és sok összehasonlítást végez az összevonáshoz képest. Bár az egyesítés rendszere kevesebb összehasonlítást igényel, további 0 (n) memóriaterületre van szükség az extra tömb tárolásához, míg a gyors rendezéshez O (log n) hely szükséges.
