Saralashning qat’iy usullari va ularning samaradorligi.
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:
x elementi kalitidan kichik kalitli a(j) element topildi.
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
Cmax
nn 1 2
ga teng bo’ladi, ya’ni
On2 . O’rinlashtirishlar soni esa
max
M max
C 3(n 1) ga teng bo’ladi, ya’ni On2 . Agar berilgan massiv o’sish tartibida
saralangan bo’lsa, u holda taqqoslashlar va o’rinlashtirishlar soni eng kichik bo’ladi,
ya’ni
Cmin
n 1 ,
M min
3(n 1) .
|
