Tartalom

• Összehasonlító táblázat
• A gyors rendezés meghatározása
• Meghatározása a Merge Sort
• Következtetés

A gyors rendezés és az összevonás szerinti algoritmusok a megosztás és meghódítás algoritmusán alapulnak, amely meglehetősen hasonló módon működik. A gyors és az egyesítés közötti előző különbség az, hogy a gyors rendezésnél a pivot elemet használják a rendezéshez. Másrészt az egyesítés rendezése nem használja a pivot elemet a rendezéshez.

Mind a válogatási technikák, a gyors rendezés és az egyesítés rendezése az osztás és meghódítás módszerére épül, amelyben az elemek halmazát elválasztják, majd átrendezés után kombinálják. A gyors rendezéshez általában több összehasonlításra van szükség, mint az egyesítéshez, ha egy nagy elemcsoportot el akar rendezni.

1. 1. Összehasonlító táblázat
   2. Meghatározás
   3. Főbb különbségek
   4. Következtetés

Összehasonlító táblázat

Az összehasonlítás alapja	Gyors rendezés	Egyesítés rendezés
Az elemek particionálása a tömbben	Az elemek listájának felosztása nem feltétlenül történik felére.	A tömböt mindig felére osztják (n / 2).
A legrosszabb eset bonyolultsága	Tovább2)	O (n log n)
Jól működik	Kisebb tömb	Finoman működik bármilyen tömbben.
Sebesség	Gyorsabb, mint a többi adatkészlet más rendezési algoritmusa.	Állandó sebesség az összes típusú adatkészletben.
További tárhely szükséges	Kevésbé	Több
Hatékonyság	Nagyobb tömbök esetén nem hatékony.	Hatékonyabb.
Rendezési módszer	Belső	Külső

A gyors rendezés meghatározása

Gyors rendezés pervazívan használt rendezési algoritmus, mivel a rövid tömbök esetében gyors. Az elemek halmaza többször fel van osztva részekre, amíg nem lehet tovább osztani. A gyors rendezés más néven partíciócsere rendezés. Az elem particionálásához kulcsfontosságú elemet (pivot néven) használ. Az egyik partíció azokat az elemeket tartalmazza, amelyek kisebbek, mint a kulcs elem. Egy másik partíció azokat az elemeket tartalmazza, amelyek nagyobbak, mint a kulcs elem. Az elemeket rekurzívan rendezzük.

Tegyük fel, hogy A egy n számú A, A, A, ..., A tömb, amelyet rendezni kell. A gyors rendezési algoritmus a következő lépésekből áll.

1. Az első elem vagy bármely kulcsként kiválasztott véletlenszerű elem feltételezzük, hogy a kulcs = A (1).
2. Az „alacsony” mutatót a második, a „fel” mutatót a tömb utolsó elemére helyezzük, azaz alacsony = 2 és fel = n;
3. Következetesen növelje az „alacsony” mutatót egy pozícióval, amíg (A> gomb).
4. Folyamatosan csökkentse a „fel” mutatót egy pozícióval, amíg (A <= gomb).
5. Ha feljebb van, mint az alacsony A cserélés A-val.
6. Ismételje meg a 3,4-es és az 5-ös lépést mindaddig, amíg az 5. lépésben a feltétel nem sikerül (vagyis felfelé = = alacsony), majd cserélje ki az A gombot.
7. Ha a kulcs bal elemei kisebbek, mint a kulcs, és a kulcs jobb oldali elemei nagyobb, mint a kulcs, akkor a tömb két al-tömbre oszlik.
8. A fenti eljárást ismételten alkalmazzák az al-tömbökre mindaddig, amíg a teljes tömb rendezésre nem kerül.

   

Előnyök és hátrányok

Jó átlagos eseti viselkedéssel rendelkezik. A gyors rendezés futási ideje nagyon bonyolult, azaz gyorsabb, mint az olyan algoritmusok, mint a buborék rendezés, a beszúrás és a kiválasztás. Ez azonban bonyolult és nagyon rekurzív, ezért nem alkalmas nagy tömbökhöz.

Meghatározása a Merge Sort

Egyesítés rendezés egy külső algoritmus, amely szintén a split and conquer stratégián alapul. Az elemeket újra és újra al-tömbökre osztják (n / 2), amíg csak egy elem marad hátra, ami jelentősen csökkenti a rendezési időt. További tárolót használ a kiegészítő tömb tárolására. Az egyesítés rendezése három tömböt használ, ahol kettőt használnak mindkét fél tárolására, a harmadik pedig a végső rendezett lista tárolására. Az egyes tömböket ezután rekurzívan osztályozzuk. Végül az al-tömböket egyesítik, hogy n a tömb elemmérete legyen. A listát mindig csak felére osztották (n / 2), amelyek nem hasonlítanak a gyors rendezéshez.

Legyen A az n számú elem tömbje, A, A, ………, A. Rendezés: Az egyesítési sorrend a megadott lépéseket követi.

1. Osszuk az A tömböt körülbelül n / 2-re osztott al-tömbbe 2-gyel, ami azt jelenti, hogy az (A, A), (A, A), (A, A), (A, A) almátrixban lévő elemeknek rendezett sorrendben legyen.
2. Kombinálja az egyes párokat, hogy megkapja a 4-es méretű válogatott alrétegek listáját; az alrétegek elemei szintén vannak rendezve (A, A, A, A), ……, (A, A, A, A), ……. (A, A, A, A).
3. A 2. lépést ismételten végrehajtjuk, amíg csak egy n méretű rendezett tömb van.

   

Előnyök és hátrányok

Az egyesítési rendezési algoritmus pontosan ugyanolyan és pontosan teljesít, függetlenül a rendezésben részt vevő elemek számától. A nagy adatkészlettel is jól működik. Ugyanakkor a memória nagyobb részét fogyasztja.

1. Az egyesítési sorrendben a tömbnek csak két részre kell osztódnia (azaz n / 2). Ellentétben a gyors rendezéssel, nincs kényszer a listát egyenlő elemekre osztani.
2. A gyors rendezés legrosszabb összetettsége az O (n²), mivel a legrosszabb állapotban sokkal több összehasonlítást igényel. Ezzel szemben az egyesítési sorrendben a legrosszabb és az átlagos eset összetettsége azonos, azaz O (n log n).
3. Az egyesítés rendezése bármilyen típusú adatkészletnél jól működik, legyen az nagy vagy kicsi. Éppen ellenkezőleg, a gyors rendezés nem működik jól nagy adatkészletek esetén.
4. Bizonyos esetekben a gyors rendezés gyorsabb, mint az egyesítés, például kis adatsorok esetén.
5. Az egyesítéshez további memória szükséges a kiegészítő tömbök tárolására. Másrészt a gyors rendezés nem igényel sok helyet az extra tároláshoz.
6. Az egyesítés hatékonyabb, mint a gyors rendezés.
7. A gyors rendezés belső rendezési módszer, ahol a rendezendő adatokat egy időben módosítják a fő memóriában. Ezzel szemben az egyesítési rendezés külső rendezési módszer, amelyben a rendezendő adatokat nem lehet egyszerre a memóriában tárolni, és néhányat a kiegészítő memóriában kell tartani.

Következtetés

A gyors rendezés gyorsabb az esetekben, de bizonyos helyzetekben nem hatékony, és sok összehasonlítást végez az egyesítési rendezéshez képest. Bár az egyesítéshez kevesebb összehasonlítást igényel, további memóriaterületre van szüksége 0 (n) az extra tömb tárolására, míg a gyors rendezéshez O (log n) helyre van szükség.