To’g’ridan-to’g’ri tanlash usuli bilan saralash

8
3. Undan keyin ushbu jarayon qolgan n-1 ta element, n-2 ta element va xokazo, toki bitta 
eng “katta” element qolguncha davom ettiriladi. 
Algoritm samaradorligi: 
Taqqoslashlar soni M = 
n
n
n
n
2
1
2
2
(
)
 

. 
Almashtirishlar soni C
min
= 3(n - 1), C
max
= 3(n - 1)
n
2
(n
2
tartib).
Ushbu usul bo’yicha saralash bajarilsa, eng yomon xolda taqqoslashlar va almashtirishlar 
soni tartibi n
2
bo’ladi. 
To’g’ridan-to’g’ri almashtirish usuli bilan saralash (pufaksimon) 
Ushbu usulni g’oyasi quyidagicha: n - 1 marta massivda quyidan yuqoriga qarab yurib 
kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik 
bo’lsa, u holda ular o’rni almashtiriladi.
Pufaksimon usulni yaxshilangan usuli bu sheyker saralash usuli bo’lib, har bir o’tishdan 
keyin sikl ichida yo’nalish o’zgartiriladi. 
Algoritm samaradorligi: 
taqqoslashlar soni M = 
n n
n
2 2
4
2
 
, 
almashtirishlar soni C
max
= 3
n
2
4
. 
Quyida biz ushbu saralash algoritmlaridan bir nechtasini ko`rib o`tamiz, shuningdek quick 
sort saralash algoritmiga keying rejamizda alohida to`xtalib o`tamiz va tushunishga harakat 
qilamiz.

9
Bubble sort saralash algoritmi qanday usulda saralash? Ushbu so`z pufakcha usulida 
saralash degan ma’noni anglatadi. Bu saralash usulida massiv elementlarining ikki qo`shni 
elementlari taqqoslanadi va agarda noto`g`ri joylashgan bo`lsa ularnung o`rinlari almashtiriladi. 
Umumiy n-1 marta ushbu jarayon bajariladi. Har safar ikkita qo`shni element taqqoslanadi. 
Yuqoridagi jarayonda har bir element o`z o`rniga siljib boradi xuddi suvdagi pufakchaga o`xshab. 
Shu sababli ham uning nomi pufakcha usulida saralash deb nomlanadi. Bu algoritmning asosiy 
g‘oyasini yozish uchun tartiblanishi kerak bo‘lgan yozuvlar vertikal joylashgan massivda 
saqlanadi deb faraz qilamiz. Kalit maydonning kichik qiymatli yozuvlari «yengil» va shuning 
uchun pufakcha kabi ular yuqoriga «suzib chiqadi». Massiv bo‘ylab birinchi o‘tishda massivning 
birinchi yozuvi olinadi va uning kaliti navbatma-navbat keyingi yozuvlarning kalitlari bilan 
solishtirib boriladi. Agar nisbatan «og‘ir» kalitli yozuvlar uchrasa, u holda bu yozuvlar joyini 
almashtiradi. Nisbatan «yengil» yozuvlar uchraganda bu yozuv taqqoslash uchun etolon bo‘ladi 
va keyingi barcha yozuvlar shu kalit bilan solishtiriladi. Natijada eng kichik qiymatli kalit 
massivning eng yuqorisiga chiqadi. Massiv bo‘ylab ikkinchi o‘tishda massivning massivni 
birinchi o‘tishda topilgan yozuvdan keyin joylashgan og‘irligi bo‘yicha ikkinchi kalit olinadi. 
Massiv bo‘ylab ikkinchi va keyingi o‘tishlarda oldingi o‘tishlarda topilgan yozuvlarni ko‘rib 
chiqish shart emas, chunki ular qolgan yozuvlarga qaraganda kichik kalitlarga ega. 
Quyida bubble sort algoritmining c++ tilidagi dasturini keltiramiz: 
#include  
using namespace std; 
int main(){ int a[100], i, j, n, t; 
cin>>n; 
for(i=0; icin>>a[i]; 
for(i=n; i>=1; i--) 
{ for(j=0; jif(a[j]>a[j+1]) 
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } 
for(i=0; icout<return 0; } 

10
Yana bir saralash usuli insertion sort bo`lib, u ham massiv elementlarini saralashda qulay 
usullardan biri hisoblanadi. Insertion sort saralash algoritmida asosan boshidan boshlab 2 ta 
elementini keyin 3 ta so`ngra 4 ta va hakozo n ta elementni tartiblanadi. (1) - qadamda dastlabki 
2 ta element tartiblanganda faqat 2 ta element, (2) - qadamda 3 ta element tartiblanganda esa 3 - 
element dastlabki 2 tasi bilan, (3) - qadamda 4 ta element tartiblanganda 4 - element dastlabki 3 
tasi bilan va hakozo (n -1) - qadamda n ta element tartiblanganda n- element dastlabki n tasi bilan 
taqqoslanadi. Bizning maqsad ham shu oxirgi qadamda bajarilgan vazifa ya’ni n ta elementni 
saralashdan iborat edi. Buni osonroq tushunish uchun quyidagi misolni keltiramiz: 
Endi esa ushbu saralash algoritmining dasturini keltiramiz: 
#include  
6
7
3
8
4
6
7
3
8
4
(1
) 
6
7
3
8
4
(2
) 
3
6
7
8
4
3
6
7
8
4
(3
) 
3
4
6
8
7
3
4
6
8
7
(4
) 
3
4
6
8
7

11
using namespace std; 
int main() 
{ int *a, i, n, j, m; 
cin >> n; 
a=new int [n]; 
for(i=0; icin>>a[i]; 
for(i=1; i{ j=i; 
while(j>0&&(a[j]{ m=a[j]; 
a[j]=a[j-1]; 
a[j-1]=m; 
j--; } } 
for(i=0; icout << a[i] << " "; 
delete []a; 
return 0; } 
Selection sort alagaritmi – bu tanlash algoritmidir. Tanlash algoritmi saralash 
algoritmlarining eng oddiy saralash usuli hisoblanadi. Ushbu saralash algoritmi ro’yhatning ikki 
qismga bo’linadigan qismi, chap tomonning oxiridagi qismi va o’ng tomonning ajralmas qismiga 
bo’linadigan joylarda taqqoslashga asoslangan saralash algoritmidir. Dastlabki holda, 
tartiblangan qism bo’sh va sarlavha qilinmagan qism butun ro’yhat hisoblanadi. Eng kichik 
eliment unsorted qatordan tanlanadi va eng chap element bilan almashtiriladi va bu element 
tartiblangan qatorning bir qismiga aylanadi. Ushbu jarayonni bajarish tartibsiz qator qatorni 
o’nga bir element bilan harakat qilishni davom ettiradi. Uishbu saralash algaritmi juda katta 
malumotlar majmui uchun mos emas, chunki urtacha va eng yamon vaziyat murakkabligi O(n
2
) 
, bu yerda n saralaniyotgan massivning elementlar sonini bildiradi. 
Quyida tanlash asosida saralash algoritmining dastur matnini C++ dasturlash tilida keltirib 
o’tamiz: 
#include  

12
using namespace std; 
int main() 
{ int *a, i, j, buf, n, t; 
cin>>n; 
a=new int[n]; 
for(i=0; icin>>a[i]; 
for(i=0; i; i++) { 
t=i; 
for(j=i+1; jif(a[t]>a[j]) { 
t=j; 
} 
} 
buf=a[t]; 
a[t]=a[i]; 
a[i]=buf; 
} 
for(i=0; icout << a[i] << " "; 
delete []a; 
return 0; } 
Dastur izohi: dastur C++ dasturlash tilining kompyuterlar uchun mo’ljallangan versiyalarida 
ishga tushirilgach hosil bolgan qora fondagi doskaga dastlab massiv elementlari soni n so’ngra n 
ta massiv elementini kiritamiz. Massivning birinchi elementi bilan qolgan barcha elementlarni 
taqqoslab chiqamiz. Agarda massivning birinchi elementi qolgan barcha elementlarni 
ixtiyoriysidan katta bo’lsa u holda bu elementlar urni almashadi. Kiyingi qadamda ikkinchi 
element bilan undan kiyin turgan elementlarni taqqoslaymiz. Kiyingi qadamda uchinchi element 
va hakozo oxirgi qadamda n-1 birinchi element bilan n-element taqqoslanadi. Har qadamda 

13
taqqoslash sharti bajarilsa taqqoslangan elementlar o’rni almashadi va bu jarayon taqqoslash 
sharti bajarilmay qolguncha davom etadi
Dastur natijasi quyidagicha bo’ladi: 

Download 0,97 Mb.