|
Algoritmlar va berilganlar strukturasi
|
səhifə | 2/4 | tarix | 19.05.2023 | ölçüsü | 0,88 Mb. | | #111385 |
| mustaqil ish2Afzalliklari
• Oddiy amalga oshirish
• Kichik ma'lumotlar uchun samarali
Moslashuvchan: Agar kiritish ro'yxati oldindan saralangan bo'lsa [to'liq bo'lmasligi mumkin], qo'shimchalar tartibi O(n + d) ni oladi, bu yerda d - inversiyalar soni • Tanlash va pufakchaga qaraganda amalda samaraliroq turlari, garchi ularning barchasida O(n 2) eng yomon holat murakkabligi.
Barqaror: Agar kalitlar (vaqt o'zgaruvchisi) bir xil bo'lsa, kiritish ma'lumotlarining nisbiy tartibini saqlaydi .
Bu faqat doimiy O(1) qo'shimcha xotira maydonini talab qiladi .Kiritish tartibi ro'yxatni qabul qilganidek saralashi mumkin.
Eng yaxshi, eng yomon va o'rtacha holatlar
Eng yaxshi holat kiritish allaqachon tartiblangan massivdir. Bu holda kiritish tartiblash chiziqli ishlash vaqtiga ega (ya'ni, O( n )). Har bir iteratsiya davomida kirishning birinchi qolgan elementi faqat massivning tartiblangan kichik bo'limining eng o'ngdagi elementi bilan solishtiriladi.
Eng oddiy eng yomon holat kiritish teskari tartibda tartiblangan massivdir. Barcha eng yomon holatlar to'plami barcha massivlardan iborat bo'lib, har bir element o'zidan oldingi elementlarning eng kichigi yoki ikkinchi eng kichigi bo'ladi. Bunday hollarda ichki halqaning har bir iteratsiyasi keyingi elementni kiritishdan oldin massivning butun saralangan bo'limini skanerlaydi va siljitadi. Bu kiritish tartibiga kvadratik ish vaqtini beradi (ya'ni, O( n 2 )).
O'rtacha registr ham kvadratik bo'lib, katta massivlarni saralash uchun qo'shish tartibini amaliy bo'lmaydi. Shu bilan birga, kiritish tartiblash juda kichik massivlarni saralashning eng tezkor algoritmlaridan biridir, hatto quicksort dan ham tezroq ; Haqiqatan ham, tezkor saralashning yaxshi ilovalari ma'lum chegaradan kichikroq massivlar uchun, shuningdek, kichik muammolar sifatida paydo bo'lganda ham qo'shish tartibidan foydalanadi; aniq chegara eksperimental tarzda aniqlanishi kerak va mashinaga bog'liq, lekin odatda o'n atrofida.
Misol: Quyidagi jadvalda {3, 7, 4, 9, 5, 2, 6, 1} ketma-ketligini saralash bosqichlari koʻrsatilgan. Har bir bosqichda ko'rib chiqilayotgan kalit ta'kidlanadi. Oldingi bosqichda ko'chirilgan (yoki joyida qoldirilgan, chunki u hali ko'rib chiqilgan eng katta kalit) yulduzcha bilan belgilangan.
3 7 4 9 5 2 6 1
3*
7 4 9 5 2 6 1
3 7* 4 9 5 2 6 1 3 4* 7 9 5 2 6 1
3 4 7 9* 5 2 6 1 3
4 5* 7 9 2 6 1
2* 3 4 5 7 9 6 1
2 3 4 5 6* 7 9 1
1* 2 3 4 5 6 7 9
Dostları ilə paylaş: |
|
|