6-ma’ruza. Saralash turlari va algoitmlar samardorligi. Saralashning qat’iy va yaxshilangan usullari. Reja

To’g’ridan-to’g’ri qo’shish usuli bilan saralash. Bunday usul karta o’yinida keng qo’llaniladi. Elementlar (kartlar) hayolan “tayyor” a(1),...,a(i-1) va boshlang’ich ketma-ketliklarga bo’linadi. Har bir qadamda (i=2 dan boshlanib, har bir qadamda bir birlikka oshirib boriladi) boshlang’ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo’shiladi.
Taklif qilinayotgan usulni quyidagi misolda ko’rib chiqamiz.
Faraz qilaylik, kalit qiymati 4, 5, 3, 8, 1, 7 bo’lgan elementlar berilgan bo’lsin.

Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo’ladi. Taqqoslashlar amalga oshirish mobaynida, navbatdagi a(j) element bilan solishtiriladi, keyin esa x bo’sh joyga qo’yiladi yoki a( j ) o’nga suriladi va jarayon chapga “ketadi”. Shuni e’tiborga olish lozimki, saralash jarayoni quyidagi shartlarni birortasi bajarilganda yakunlanadi:
1. x elementi kalitidan kichik kalitli a(j) element topildi.
2. tayyor ketma-ketlikning chap tomoni oxiriga yetib borildi.
Taklif etilayotgan usul algoritmi quyidagicha bo’ladi:
for (int i=1;i
int j=i;
while(a[j]
int t=a[j-1];
a[j-1]=a[j];
a[j]=t;
j=j-1;
}
}
Algoritm samaradorligi
Faraz qilaylik, taqqoslashlar soni S, o’rinlashtirishlar soni M bo’lsin. Agar massiv elementlari kamayish tartibida bo’lsa, u holda taqqqoslashlar soni eng katta bo’lib, u ga teng bo’ladi, ya’ni . O’rinlashtirishlar soni esa ga teng bo’ladi, ya’ni . Agar berilgan massiv o’sish tartibida saralangan bo’lsa, u holda taqqoslashlar va o’rinlashtirishlar soni eng kichik bo’ladi, ya’ni , .
To’g’ridan-to’g’ri tanlash usuli bilan saralash. Faraz qilaylik, a₁, a₂, … , a_n elementlar ketma-ketligi berilgan bo’lsin.
Mazkur usul quyidagi tamoyillarga asoslangan:
1. Berilgan elementlar ichidan eng kichik kalitga ega element tanlanadi.
2. Ushbu element boshlang’ich ketma-ketlikdagi birinchi element a₁ bilan o’rin almashadi.
3. Undan keyin ushbu jarayon qolgan n-1 ta element, n-2 ta element va xokazo, toki bitta eng “katta” element qolguncha davom ettiriladi.
Taklif qilinayotgan usul algoritmi quyidagicha bo’ladi:
C++ tilidagi dasturi:
for(int i=0;i
for(int j=i+1;j
if (a[i] > a[j]){
int k = a[j];
a[j]= a[i];
a[i]= k;
}