Shellsort aslida insertion sort‘ning o’zgargan shakli. U dastlab ro’yhatni (array) birnecha kichik bo’laklarini (sublist), so’ngra ularni alohida holda insertion sort metodida tartiblaydi. Ro’yhatning bo’laklarini (sublist’larini) tartiblash uchun «increment» deb nomlangan h son hosil qilinadi. Ro’yhat tartiblanib bo’lingach, so’nggi bosqichda insertion sort ishlatiladi.
h increment soni talablari:
- u kamaytirib borilganda, ohirgi qiymati 1 bo’lishi kerak, shunda so’nggi bosqichda insertion sort’ni ishlatish mumkin bo’ladi.
- effektivlik yuqori bo’lishi uchun imkoni boricha takroriy almashtirishlardan qochish imkonini beradigan son bo’lsin.
h soni uchun ko’p ishlatiladigan formula – h = 3*h + 1 (Knuth formulasi). Bunda qadamlar 1, 4, 13, 40, … .
Shuningdek, eng effektiv qadam – 701, 301, 132, 57, 23, 10, 4, 1. (Ciura). Ammo buni formulaga solishning imkoni yo’q.
Yuqoridagilarni o’qib tushunib olish qiyin, to’g’ri. Misol bilan tushuntirishga harakat qilaman.
Bizda tartiblanmagan array bor:
[ 12 8 0 4 7 10 4 19 11 21 15 1 6 5 ]
Uni Shellsort’da, incrementlarni Knuth formulasi yordamida topib tartiblaymiz.
Array uzunligi – 14. Ushbu array uchun h ning maksimum qiymatini topamiz:
let h = 1 while (h < arr.length / 3) h = 3*h + 1
h = 13 ga teng bo’ladi.
Demak dastlab, array’ning nolinchi va 13-elementlarini solishtirib, tartiblaymiz.
12 8 0 4 7 10 4 19 11 21 15 1 6 5
12 > 5, ularning o’rnini almashtiramiz:
5 8 0 4 7 10 4 19 11 21 15 1 6 12
h ni 3 ga bo’lib, butun qiymatini olamiz (katta tarafga qarab yaxlitlamaymiz, butun qismini olamiz). h = 13 / 3 = 4. Keyingi tartiblash oralig’i h = 4 bo’ladi.
5 8 0 4 7 10 4 19 11 21 15 1 6 12
h = 4 oraliqni 14 ta elementli array’da 3ta siklda tartiblaymiz.
Birinchi siklda:
5 8 0 4 7 10 4 19 11 21 15 1 6 12
4 < 19 – elemetlar joyida qoladi. 19 > 1 – ularning o’rni almashadi.
5 8 0 4 7 10 4 1 11 21 15 19 6 12
4 > 1, elementlarning o’rni almashadi.
5 8 0 1 7 10 4 4 11 21 15 19 6 12
– – –
Ikkinchi siklda:
5 8 0 1 7 10 4 4 11 21 15 19 6 12
5 < 7 – elementlar joyida qoladi. 7 < 11 – elementlar joyida qoladi. 11 > 6 – ularning o’rni almashadi:
5 8 0 1 7 10 4 4 6 21 15 19 11 12
7 > 6 – ularning o’rni almashadi:
5 8 0 1 6 10 4 4 7 21 15 19 11 12
– – –
Uchinchi siklda:
5 8 0 1 6 10 4 4 7 21 15 19 11 12
8 < 10, elemeentlar joyida qoladi. 10 < 21, elementlar joyida qoladi, 21 > 12, elementlar o’rni almashadi:
5 8 0 1 6 10 4 4 7 12 15 19 11 21
h = 4 bo’lgandagi 3ta sikl yakunlandi. Biz h ni yana 3 ga bo’lib, butun qiymatini olamiz. h = 4 / 3 = 1. Keyingi tartiblash oralig’i h = 1 bo’ladi. Bizda katta qadamlar bo’yicha tartiblash yakunlandi, ya’ni insertion sortga yetib keldik. Dastlabki array:
[ 12 8 0 4 7 10 4 19 11 21 15 1 6 5 ]
h-qadamli tartiblangach:
[ 5 8 0 1 6 10 4 4 7 12 15 19 11 21 ]
ga o’zgardi.
Insertion sortdan keyin esa to’liq tartiblanadi:
[ 0 1 4 4 5 6 7 8 10 11 12 15 19 21 ]
Shellsort’ning insertion sort’dan ustunligi nimada?
Nima uchun dastlab h qadamli tartiblashni amalga oshirdik?
Qadamli tartiblash bilan biz insertion sort’ga almashtirishlar sonini kamaytirib berdik, shu tariqa biz insertion sortning algoritmining ishlash vaqtini tezlashtirdik. Solishtirish uchun, insertion sort’da upper bound O(N2) bo’lsa, shellsort’da Knuth formulasi orqali qadamli tartiblab olib, upper bound’ni O(N3/2) ga tushirdik. Kichik array’larda vaqtdagi o’zgarishni sezishning imkoni yo’q, ammo 10 000, 100 000 elementli array’larni tartiblashda Shellsortning ustunligi ko’rinadi.
Kod:
Note: Funksiya faqat integer sonlarni to’g’ri tartiblaydi. Harflarni yoki string sonlarni to’g’ri tartiblash uchun «>» dan boshqa amalni ishlatish kerak. Masalan, ES6 uchun String.prototype.localeCompare() ni ishlatib ko’ring.
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sorts/shellsort.js
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin:
