|
Tez tartiblashning afzalliklari
|
| bet | 12/16 | | Sana | 15.11.2023 | | Hajmi | 29,81 Mb. | | #99092 |
Bog'liq Dilshoda Algoritm mustaqil Tez tartiblashning afzalliklari:
Bu “bo‘l va zabt et” algoritmi bo‘lib, muammolarni hal qilishni osonlashtiradi.
Katta ma'lumotlar to'plamlarida samarali.
Uning ishlashi uchun faqat kichik hajmdagi xotira kerak bo'lganligi sababli, u past yukga ega.
Tez tartiblashning kamchiliklari:
U eng yomon vaqt murakkabligi O(N 2 ) ga ega, bu pivot noto'g'ri tanlanganda yuzaga keladi.
Kichik ma'lumotlar to'plamlari uchun bu yaxshi tanlov emas.
Bu barqaror tartib emas, ya'ni agar ikkita element bir xil kalitga ega bo'lsa, tezkor saralashda ularning nisbiy tartibi tartiblangan chiqishda saqlanmaydi, chunki bu erda biz elementlarni pivot holatiga ko'ra almashtiramiz (ularning asl holatini hisobga olmagan holda). pozitsiyalar).
Ko'p ortiqcha elementlarga ega massivni ko'rib chiqing. Masalan, {1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 4, 4, 4}. Simple QuickSort-da pivot sifatida 4 tanlansa, biz faqat bitta 4 ni tuzatamiz va qolgan hodisalarni rekursiv qayta ishlaymiz. 3 Way QuickSort-da arr[l..r] massivi 3 qismga bo'linadi:
arr[l..i] elementlar pivotdan kichik.
arr[i+1..j-1] elementlar pivotga teng.
arr[j..r] elementlar pivotdan katta.
Xulosa:
Xulosa qilib aytish mumkinki, Quicksort bu tez va samarali saralash algoritmi bo'lib, o'rtacha vaqt murakkabligi O(N logN). Bu asl masalani yechish osonroq bo‘lgan kichikroq kichik muammolarga ajratuvchi algoritm. U iterativ va rekursiv shakllarda osonlik bilan amalga oshirilishi mumkin va u katta ma'lumotlar to'plamlarida samarali bo'ladi va ma'lumotlarni joyida saralash uchun ishlatilishi mumkin. Shu bilan birga, uning kamchiliklari ham bor, masalan, pivot noto'g'ri tanlanganda yuzaga keladigan O(N 2 ) ning eng yomon vaqt murakkabligi. Quicksortning ishlashi pivot tanlashga sezgir.
|
| |
