4-Mavzu: Kvadratik, logarifmik va chiziqli qiyinchilikdagi saralash algoritmlari Shell sort

4-Mavzu: Kvadratik, logarifmik va chiziqli qiyinchilikdagi saralash algoritmlari
Shell sort. Shell sort algoritmi Donald Shell tomonidan yaratilgan tartiblash algoritmidir. Bu algoritm joylash usulida tartiblashning umumlashgan variantidir. Joylash usulida tartiblash berilganlar deyarli tartiblangan ketma ketlikda berilgan holatda samarali ishlaydi. Ya’ni biror qismigina tartiblanmagan bo’lsa yaxshi ishlashi mumkin. Shell sort n bo’shliq algoritmi sifatida ham ishlatilishi mumkin. Bunda faqat qo’shni elementlarni o’rniga bir nechta qadam uzoqlikda joylashgan elementlarni ham solishtirish orqali tartiblash amalga oshiriladi. Bu qo’shni elementlar orasida bo’shliq yuzaga kelishiga olib keladi.
Joylash usulida tartiblashda solishtirish faqat qo’shni elementlar orasida amalga oshiriladi. Har bir solishtirishda ko’pi bilan 1 ta invariant hosil qilinishi mumkin. Shell sort algoritmining g’oyasiga ko’ra oxirgi qadamgacha qo’shni elementlar solishtirilmaydi. Ya’ni algoritmning so’ngi qadamidagina qo’shni elementlar solishtiriladi. Bu esa joylash usulida tartiblash algoritmiga bir biridan uzoqda joylashgan elementlarniyam solishtirish imkonini berish orqali uning samaradorligini oshirishdir. Demak shell sort algoritmi joylash usulida saralash algoritmining kengaytirilgan(samaradorligi oshirilgan) ko’rinishidir.
Algoritmning asosiy g’oyasi shundan iboratki massivdagi har bir h-elementni joyini o’zgartirishdir. h qancha uzoqlikdagi elementlarning joyi o’zgarishi mumkinligini bildiradi. Aytaylik h=13 bo’lsin. U holda birinchi (0-indeksdagi) element bilan 14-element (13-indeksdagi) bilan o’rin almashishi mumkin (agar zarur bo’lsa). Ikkinchi element 15-element bilan va hokazo. Agar h=1 bo’lsa joylash usulida tartiblashning o’zi bo’ladi.
Shell sort yetarlicha katta(elementlar sonidan kichik) h bilan boshlanadi. Joriy h uchun massiv to’liq tartiblangach h tartiblangan massiv hosil bo’ladi. Keyingi qadamda h biror ketma ketlik bo’yicha kamaytiriladi va keyingi h tartiblangan massiv hosil bo’ladi. Qachonki h birga teng bo’lsa va h tartiblangan massiv hosil bo’lsa massiv to’liq tartiblangan bo’ladi. Biroq bu bosqichda massiv deyarli tartiblangan holatga kelib qolgan va tartiblash uchun qulay ko’rinish hosil bo’lgan bo’ladi.
void ShellSort(int a[], int size){
int i, j, h, v;
for (h = 1; h = size / 9; h = 3 * h + 1){
for (;h>0;h=h/3){
for (i = h + 1; i = size; i += 1){
v = a[i];
j = i;
while (j > h && a[j - h] > v){
a[j] = a[j - h];
j -= h;
}
a[j] = v;
}
}
}
}