Saralash usullari mavzusi bo’yicha ma’ruza matni

2.1.6. Shell saralash usuli

9-rasmda Shell saralash usuli namoyish etilgan:



9-Rasm. Shell saralash usuli
Birinchi o’tishda bir-biridan to’rt pozitsiyadan ajiratiladigan barcha elementlar alohida guruhlanadi va saralanadi. Bu jarayon 4-saralash deyiladi. Bizning misolimizdagi sakkizta elementdan har bir guruh ikki elementni o’z ichiga oladi. Shundan so’ng elementlar bir-biridan ikki pozitsiyaga ajiratiladigan elementlar bilan guruhga birlashtiriladi va yangidan saralanadi. Bu jarayon 2-saralash deyiladi. Nihoyat uchinchi o’tishda barcha elementlar odatdagidek 1-saralashni kiritib saralanadi.
Saralashda har bir qadamda yoki nisbatan kam elementlar qatnashadi yoki ular alloqachon yaxshi tartiblangan va nisbatan kam almashtirishlarni talab qiladi. Shubhasiz, bu usul saralangan massivni beradi, va shuningdek, har bir o’tishda oldingi o’tishning natijalari foydalanilishi aniq tushunarli, har bir i-saralash oldingi 2i-saralashdagi saralangan ikki guruhni birlashtiradi.
Shuningdek, agar oxiri birga teng iqtiyoriy ketme-ketlikning ortib ketishi maqbul ekalnigi aniq, chunki eng yoman holatda barcha ishlar eng oxirgi o’tishda bajariladi. Ammo ortib ketishi ikki barabar bo’lganda, orttirishning kamayish usuli ham yaxshi natija berishi kichikroq ekanligi aniq. Shunday qilib, dastur konkret ketme-ketlikning ortishi bilan aloqadan tashqari ishlab chiqariladi. Barsha t orttirma va bilan ifodalanadi.
Har bir h – saralash oddiy kiritish bilan saralash kabi dasturlashtiriladi, bunda qodiruvning tulallanish sharti uchin kiritish joyiga oddiygina to’siq qo’yiladi. Har bir h saralash xususiy to’siq talab qilishi va dastur uning joyini iloji boricha aniqlash kerakligi tushinarli.

2.1.7. Almashish bilan murakkab saralash (Хоор saralash usuli)

Aslida Xoor saralash usuli eng yuqori samaradarlikka erishish uchun katta masofada elementlar almashishini ishlab chiqarish maqsadga muvofiq. U quyidagi algoritm asosida amalga oshiriladi: mediana deb nomlanuvchi massivning iqtiyoriy erikli elementi tanlanadi, keyin massiv chapdan o’ngga qadar tanlanganidan kattaroq element topulmaguncha qarab chiqiladi; keyin esa massiv o’ngdan chapga qadar tanlanganidan kichik element topulmaguncha qarab chiqiladi. Topilgan elementlar joylarini almashtiradi. Keyin “almashish bilan ko’rish” jarayoni hali ikki ko'rish massivning ortasining qayeridadir uchrashmaguncha davom ettiriladi. Natijada massiv ikki qismga bo’linadi: chap tomoni – tanlangan elementning kichik kaliti bilan; va o’ng tomoni – katta kaliti bilan.
Kutilayotgan almastirishlar soni taxminan n/6 ga teng. Tez saralash haligacha o’zining “makr” iga ega. Eng avvola, barcha takomillashtirilgan usullar sifatida ham n kichik qiymatlari uchun uning samaradorligi past. Uning afzalligi taqqoslash bo’yicha boshqa takomillashtirilgan usullar bilan taqsimlangan kichik qism massivlarni saralash uchun har qanday usulni osongina foydalanish mumkin