Tartiblash va saralash algoritmlari

2. Tartiblash algoritmlari
Umuman tartiblash deganda berilgan ob’yektlar to’plamini ma’lum tartibda joylash uchun qayta ishlash jarayoni tushuniladi.
Tartiblash natijasida to’plamdagi elementlarni izlash jarayonlari yengillashadi. Undan tashqari tartiblashlar misolida qanday qilib algoritmni murakkablash evaziga samaradorlikni oshirishga erishish mumkinligini ko’rsatsa bo’ladi.
Hozirgi kunda ko’pgina tartiblash algoritmlari mavjud. Algoritmni tanlash qayta ishlanayotgan ma’lumotlar strukturasiga bog’liq va shu sababli tartiblash usullari asosan 2 sinfga ajratiladi. Bular massivlarni tartiblash va fayllarni tartiblash. Ularni yana ichki va tashqi tartiblash ham deb nomlaydilar.Chunki massivlar mashinaning tezkor xotirasida joylashadi. Fayllar esa odatda ancha hajmi katta bo’lgan lekin sekin ishlaydigan tashqi xotiradan olinadilar.
Eng yahshi tartiblash algoritmlaridan biri deb Ch. Xoara usuli hisoblanadi. Bu usul almashuvga asoslangan.
Bu yerda yahshi samaradorlikka erishish uchun dastlab katta masofadagi ya’ni bir-biriga eng uzoq joylashgan elementlarni almashtirish qo’llaniladi. Faraz qilaylik bizda n ta element kalitlar bo’yicha qayta tartibda berilgan. Xoara usuli bo’yicha ularni ta almashuv bilan tartiblash mumkin. Buning uchun dastlab eng chap va eng o’ng tomonda joylashgan elementlarni almashtiramiz. Keyin ikki tomondan o’rtaga qarab kelamiz. Lekin bu faqatgina qayta tartib aniq bo’lganda amalga oshiriladi.
Endi massiv ixtiyoriy tartibda berilgan bo’lsin. Ixtiyoriy X elementni tanlab massivni chapdan o’ngga qandaydir a_i>x element uchramaguncha ko’rib chiqamiz. Keyin massivni o’ngdan chapga qandaydir a_jelement uchramaguncha o’tamiz.
a_i va a_j elementlarni o’rinlarini almashtirib massivni ikki tomondan ko’rib chiqish jarayonini massiv o’rtasiga kelmaguncha davom ettiramiz. Natijada massiv 2 qismga bo’linadi. Chap qismdagi elementlar x dan katta yoki teng bo’ladilar. O’ng tomondagi elementlar x dan kichik yoki teng bo’ladi.
Dastur tuzayotganda bu jarayonni prosedura yordamida amalga oshirish mumkin. Prosedurani rekursiv va norekursiv usullar bilan tuzish mumkin.
Quyidagi dastur rekursiv prosedurani qo’llaydi.
Prosedure Hoare;
Prosedure sort (L, R: index);
var i, j: index; w, x: item;
begin i:=L; j:=R; x:=a[(L+R) div 2];
repeat
while a[i]while a[j]>x do j:=j+1 end;
if i<=j then
begin w:=a[i]; a[i]:=a[j]; a[j]:=w;
i:=i+1; j:=j-1; end;
until i>j
if Lif iend {*sort*};
begin sort (1, n);
end {* Hoare*};
Norekursiv dasturni tuzish uchun yordamchi steklardan foydalaniladi.
Xoara algoritmni unumdorligini tahlil qilamiz. Boshlab bo’linish jarayonini ko’raylik. Qandaydir x ni tanlab biz massivni to’liq o’tamiz. Demak, n ta taqqoslashni amalga oshiramiz. Taqqoslashlarni umumiy soni n*log(n) ekanligi, o’rin almashtirishlar soni esa ekanligi isbotlangan.
Bizning misolimizda x - o’rtancha element deb tanlangan, lekin Xoara fikri bo’yicha X ixtiyoriy tanlanishi kerak. Xoara algoritmning o’rtacha ishlash vaqti teng.
Eng oson va oddiy tartiblash algoritmlaridan biri – Insertion sort. U array elementlarini solishtirib, elementlarning o’rnini almashtirish hisobiga tartiblaydi.