#5 Shell sortirovka usılı. Shell

#5 Shell sortirovka usılı.

Shell usili járdeminde sortlaw Donald L.Shell tárepinen oylap tabilǵan. Onıń ózgesheligi sonnan ibarat bunda dizimdi aralastırıp massivlerdi dizim astı esabında kórip shiǵadı. Birinshi basqıshda bul dizim astı dizimler elementlerdi juplaydı. Ekinshi basqıshda hár bir gruppada tórt elementen bar boladı. Protsess takrarlanǵanda hár bir kishi dizimdegi elementler sanı kóbeyip baradı, al tómengi dizimler sani sáykes túrde kemeyedi.

Su’wret 1
Su’wrette 1 dizimde 16 elemntti sortlawda isletiletin mu’mkin bolǵan ishki dizimdi kórsetilgen.
Su’wrette (a) segiz tómengi dizimdi kórsetilgen, olardiń hár ekewinde eki element bar boladi, onda birinshi tómendi dizim birinshi hám toǵizinshi elementlerdi, ekinshi tómengi dizimde ekinshi hám oninshi elementti óz ishine aladi h.t.b.
Su’wrette (b) biz bunda hár birinde tórt elementtiń tórt tómengi dizimin kórip turmiz. Bunda birinshi tómengi dizim birinshi, besinshi, toqqizinshi hám on u’shinshi elementlerden ibarat boldi.
Su’wrette (c) jup sanlardan ibarat bolǵan eki ishki dizimdi kórsetedi.
Su’wrette (d) bunda biz jáne qanday da bir dizimge qaytamiz.

Shell usilinda sortlawdiń java programmalastiriw tilinde jazilǵan kodi tómendegishe:

public static void sort (int[] arr)
{
for (int inc = arr.length / 2; inc >= 1; inc = inc / 2)
for (int step = 0; step < inc; step++)
insertionSort (arr, step, inc);
System.out.println(Arrays.toString(arr));
}

private static void insertionSort (int[] arr, int start, int inc)

{
int tmp;
for (int i = start; i < arr.length - 1; i += inc)
for (int j = Math.min(i+inc, arr.length-1); j-inc >= 0; j = j-inc)
if (arr[j - inc] > arr[j])
{
tmp = arr[j];
arr[j] = arr[j-inc];
arr[j-inc] = tmp;
}
else break;
}

Algoritm analizi:
insertionSort metodin shaqiriwdan baslaymiz hám metodti hár bir shaqirǵanda elementlerdiń sanlarin esaplawdan baslaymiz. Dizimniń uzinliǵI 15. Birinshi qádemde ózgeriwshi inc teń boladi 7, sonliqdan eki uzinliqda jeti qádem shaqiriladi. Ekinshi qádemde inc ózgeriwshi 3 teń boladi, sonliqdan 5 uzinliqda dizimde u’sh shaqiriw boladi. U’shinshi hám sońǵI basqishda 15 uzinliqqa teń bolǵan dizimge bir shaqiriw boladi. AldinǵI nátiyjelerden kórinip tur insertionSort algoritminde dizimdegi eki elementten eń jaman jaǵdaylardi teńlestiredi. Dizimdegi eń jaman jaǵdaylardi teńlestiriwlar sani 5 elementten 10 ǵa teń boladi. Dizimdegi eń jaman jaǵdaylardi teńlestiriwlar sani 15 elementten 105 ǵa teń boladi. Bul sanlardi qosiw nátiyjesinde bizler 142 (7 • 1 + 3 • 10 + 1 • 105) teńlestiriwler sanin alamiz. Sortlaw algoritmlerin analizlegen jaǵdayda dizimdegi inversiyalar sanin esaplaymiz. Inversiya – bul naduris tártipte ketip baratirǵan jup elementler dizimi. Misali ushin: [3,2,4,1] dizimde tórt inversiya bar, yaǵniy (3,2), (3,1), (2,1) hám (4,1). Kóplegen inversiyalardi biz teris tártipte jaylasqan tizimde kóriwge boladi, olardiń sani (N2 — N)/1 teń boladi.
Sortlaw algoritminiń analiz qiliwiniń bir usuli bul sortlanbaǵan dizimde dástlepki jaǵdaydi ajratip turatin inversialar sanin esaplaw bolip tabiladi. Algoritmdegi elementlerdiń hár bir ózgerisi inversiya sanin keminde birge kemeytedi. Eger misali ushin salistiriw nátiyjesinde janindaǵI elementler naduris tártipte ketip baratirǵanliǵI aniqlansa, olardiń qayta tártipleniwi inversiyalar sanin birme bir birge kemeytiredi. Qosimshalar boyinsha tártipleniw ushin da sonday jaǵday boladi, sebebi u’lken elementti joqari qaray jiljitiw, ózgertirilgen Hám qosilǵan elementlerdiń payda etken invertsiyani joq etedi.
Sonliqtan kóbiksheli hám tańlaw usilijárdeminde sortlawda hár qanday salistiriwlar keminde bir inversiyani alip taslawǵa tuwra keledi. Shell usilinda sortlaydiń tu’p tiykarinda ornina qoyiw usili járdeminde sortlaw algoritmi bar, sonliqtanda joqarida aytip óten jaǵday birdey tiyisli boladi.
Biraq shell usulinda sortlaw di esapqa alsaq bólek salistirw nátiyjesinde elementlerdiń óz-ara almasiwin inversiyalar sanin birewden kemeytiriw mu’mkin.
Shell usulinda sortlawdi analizlew qiyin sebebi elementlerdiń bir tu’rde ózgerisleri 14 elementti óz ishine alǵan jetti taza inversiya payda boliwin alip keledi. Sonday bolsa da inversiyalardiń sani birge qisqaradi. Eger siz 7 yamasa 4 elementlerdiń permutatsiyasina qarasańiz nátiyje birdey boladi. Biraq uliwma alǵanda jaǵday jaqsilanbaydi. Birinshi basqishda segiz salistiriwdan soń 36 inversiya alip taslanadi. Ekinshi basqishda 19 salistiriwlar ámelge asiriladi hám 24 inversiya alip taslanadi. Hám eń sońǵI basqishda 19 salistiriw ámelge asiriladi hám sońǵo 10 inversiya alip taslanadi. Salistiriwlardiń uluwmaliq sani 62. Eger biz ornina qoyiw usuli járdeminde sorlawdiń analizin shaqirǵanda eń jaman jaǵday retinde 152 salistiriwlar sani bolar edi.