Ebben a cikkben a különböző rendezési technikák fontos tulajdonságait tárgyaljuk, beleértve azok komplexitását, stabilitását és memóriakorlátjait. Mielőtt megértené ezt a cikket, meg kell értenie a különböző rendezési technikák alapjait (lásd : Rendezési technikák).
Az időbonyolultság elemzése –
Megtárgyaltuk a különböző rendezési technikák legjobb, átlagos és legrosszabb esetre vonatkozó bonyolultságát a lehetséges forgatókönyvekkel.
Összehasonlítás alapú rendezés –
Az összehasonlítás alapú rendezésben egy tömb elemeit hasonlítjuk össze egymással, hogy megtaláljuk a rendezett tömböt.
- Bubble sort és Insertion sort –
Az átlagos és a legrosszabb eset időbonyolultsága: n^2
A legjobb eset időbonyolultsága: n, ha a tömb már rendezett.
Legrosszabb eset: ha a tömb fordítva van rendezve. - Selection sort –
Jó, átlagos és legrosszabb eset időbonyolultsága: n^2, ami független az adatok eloszlásától. - Merge sort –
A legjobb, átlagos és legrosszabb eset időbonyolultsága: nlogn, ami független az adatok eloszlásától. - Heap sort –
A legjobb, átlagos és legrosszabb eset időbonyolultsága: nlogn, ami független az adatok eloszlásától. - Quick sort –
Egy oszd meg és uralkodj megközelítés rekurzív relációval:T(n) = T(k) + T(n-k-1) + cn
Legrosszabb eset: a tömb rendezése vagy fordított rendezése esetén a partíciós algoritmus a tömböt két 0 és n-1 elemű altömbre osztja. Ezért
T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)
A legjobb eset és az átlagos eset: Átlagosan a partícionáló algoritmus a tömböt két azonos méretű altáblára osztja. Ezért,
T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)
Nem összehasonlításon alapuló rendezés –
A nem összehasonlításon alapuló rendezésben a tömb elemeit nem hasonlítjuk össze egymással a rendezett tömb megtalálásához.
- Radix rendezés –
A legjobb, átlagos és legrosszabb eset időbonyolultsága: nk, ahol k a tömb elemeinek maximális számjegyeinek száma. - Számláló rendezés –
A legjobb, átlagos és legrosszabb eset időbonyolultsága: n+k, ahol k a számolótömb mérete. - Bucket sort –
A legjobb és átlagos időbonyolultság: n+k, ahol k a vödrök száma.
Rontott eset időbonyolultság: n^2, ha minden elem ugyanabba a vödörbe tartozik.
In-place/Outplace technika –
A rendezési technika akkor inplace, ha nem használ extra memóriát a tömb rendezéséhez.
A tárgyalt összehasonlításon alapuló technikák közül csak az összevonás szerinti rendezés az outplaced technika, mivel a rendezett altáblák összevonásához egy extra tömbre van szükség.
A tárgyalt nem összehasonlításon alapuló technikák közül mindegyik outplaced technika. A számláló rendezés egy számláló tömböt használ, a bucket sort pedig egy hash-táblát a tömb rendezéséhez.
Online/Offline technika –
Egy rendezési technika akkor tekinthető Online-nak, ha az eljárás közben is képes új adatokat fogadni, azaz a rendezési művelet megkezdéséhez nem szükségesek teljes adatok.
A tárgyalt összehasonlításon alapuló technikák közül csak az Insertion Sort felel meg ennek, az általa használt alapalgoritmus miatt, azaz. a tömböt (nem csak az elemeket) balról jobbra haladva dolgozza fel, és ha jobbra új elemeket adunk hozzá, az nem befolyásolja a folyamatban lévő műveletet.
Stabil/ingadozó technika –
A rendezési technika akkor stabil, ha nem változtatja meg az azonos értékű elemek sorrendjét.
Az összehasonlításon alapuló technikák közül a bubble sort, a insertion sort és a merge sort stabil technikák. A kiválasztási rendezés instabil, mivel megváltoztathatja az azonos értékű elemek sorrendjét. Vegyük például a 4, 4, 1, 3 tömböt.
Az első iterációban a legkisebb talált elem az 1, és a 0. pozícióban felcserélődik a 4-gyel. Ezért a 4 sorrendje az 1. pozícióban lévő 4-hez képest megváltozik. Hasonlóképpen a quick sort és a heap sort is instabil.
A nem összehasonlításon alapuló technikák közül a Counting sort és a Bucket sort stabil rendezési technikák, míg a radix sort stabilitása a rendezéshez használt mögöttes algoritmustól függ.
A rendezési technikák elemzése :
- Ha a tömb már majdnem rendezett, akkor az insertion sort előnyben részesíthető.
- Ha a bemenet sorrendje nem ismert, akkor a merge sort előnyben részesíthető, mivel a legrosszabb esetben nlogn időbonyolultságú és stabil is.
- Ha a tömb már rendezett, az insertion és a bubble sort n komplexitást ad, de a quick sort n^2 komplexitást ad.
Que – 1. Melyik rendezési algoritmus veszi igénybe a legkevesebb időt, ha a bemeneti tömb minden eleme azonos? Tekintsük a rendezési algoritmusok tipikus megvalósításait.
(A) Insertion Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort
megoldás: A tárgyaltak szerint a beszúrási rendezés bonyolultsága n lesz, ha a bemeneti tömb már rendezett.
Que – 2. Tekintsük a Quicksort algoritmust. Tegyük fel, hogy létezik egy olyan eljárás a pivot elem megtalálására, amely a listát két olyan részlistára osztja, amelyek mindegyike tartalmazza az elemek legalább egyötödét. Legyen T(n) az n elem rendezéséhez szükséges összehasonlítások száma. Ekkor (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
megoldás:
T(n) = T(k) + T(n-k-1) + cn
A kérdésben megadottak szerint az egyik lista az összes elem 1/5-ét tartalmazza. Ezért egy másik lista az összes elem 4/5-ét fogja tartalmazni. Az értékeket behelyettesítve megkapjuk:
T(n) = T(n/5) + T(4n/5) + cn, ami megfelel a (B) lehetőségnek.
Idő- és térbonyolultsági összehasonlító táblázat :
| Válogató algoritmus | Időbonyolultság | Térbonyolultság | |||
|---|---|---|---|---|---|
| Best Case | Átlagosan Case | Worst Case | Worst Case | ||
| Bubble Sort | Ω(N) | Θ(N2) | O(N2) | O(N2) | O(1) |
| Szelekciós rendezés | Ω(N2) | Θ(N2) | O(N2) | O(1) | |
| Behelyezési rendezés | Ω(N) | Θ(N2) | O(N2) | O(1) | |
| Merge Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) | |
| Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N log N) | O(1) |
| Gyors rendezés | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) | |
| Radix rendezés | Ω(N k) | Θ(N k) | O(N k) | O(N + k) | |
| Count Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(N + k) | O(k) |
| Bucket Sort | Ω(N + k) | Θ(N + k) | O(N 2) | O(N) | |
