void selectionSort(int arr[], int n)

61 
{
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}
Ushbu algoritmlarning elementlari soni bir xil boʻlgan holatda 
qanday vaqt ichida bajarilishi va sarflangan xotira hajmi haqidagi 
qiyosiy jadval quyida berilgan. 
Sinov oʻtkaziladigan kompyuter quyidagi xususiyatlarga ega: AMD 
A6-3400M 4x1.4 GHz, 8 Gb operativ xotira, Windows 10 x64 build 
10586.36. 
2-jadval. 
Turli saralash algortimlarining toʻliq saralanmagan massiv 
uchun ishlash vaqti va ishlatilgan xotira sigʻimi 
Saralash usuli 
10 ta element 
uchun 
50 ta element 
uchun 
200 ta element 
uchun 
1000 ta 
element uchun 
Vaqt 
(ms)
Xotira 
(K) 
Vaqt 
(ms)
Xotira 
(K) 
Vaqt 
(ms)
Xotira 
(K) 
Vaqt 
(ms)
Xotira 
(K) 
Tanlash 
boʻyicha 
saralash 
Selection 
sort 
13
510K 
37
637
118
854
550
936
Pufakchali 
saralash 
Bubble sort 
11
524
37
629
116
863
564
932
Joylashtirish 
boʻyicha 
saralash 
Insertion 
sort 
12
512
38
641
116
849
556
928
Taroqsimon 
saralash 
Comb sort 
12
505
37
632
117
854
560
936
Qisman tartiblangan massiv (elementlarning yarmi saralangan): 

62 
3-jadval.
Turli saralash algortimlarining qisman saralangan massiv 
uchun ishlash vaqti va ishlatilgan xotira sigʻimi 
Saralash usuli 
10 ta element 
uchun 
50 ta element 
uchun 
200 ta element 
uchun 
1000 ta 
element uchun 
Vaqt 
(ms) 
Xotira 
(K) 
Vaqt 
(ms) 
Xotira 
(K) 
Vaqt 
(ms) 
Xotira 
(K) 
Vaqt 
(ms) 
Xotira 
(K) 
Tanlash 
boʻyicha 
saralash 
Selection 
sort 
10
501
32
612
113
823
498
942
Pufakchali 
saralash 
Bubble sort 
9
498
32
601
110
812
509
939
Joylashtirish 
boʻyicha 
saralash 
Insertion 
sort 
9
482
31
597
112
802
502
920
Taroqsimon 
saralash 
Comb sort 
10
498
33
563
116
601
505
907
Mavzu yuzasidan savollar: 
1.
 
Tartiblash va saralash tushunchalariga ta‘rif bering 
2.
 
Tanlash boʻyicha saralash algoritmining murakkabligini baholang 
3.
 
Taroqsimon saralash va pufakchali saralash oʻrtasidagi 
oʻxshashliklarni keltiring 
4.
 
Saralash algoritmlari qanday yondashuvlar asosida baholanadi? 
5.
 
Yuqorida keltirilganlardan tashqari yana qanday saralash 
algoritmlarini bilasiz? 
 
 

63 
4-§ Birlashtirib saralash algoritmlari 
Merge sort algoritmi.
Birlashtirib saralash (Merge sort)
– 
tartiblashning tezkor bajariladigan algoritmlaridan biri. Ushbu tartiblash 
―boʻlib tashla va hukmronlik qil‖ prinsipining yaxshi namunasidir. 
Birinchidan, vazifa bir nechta kichik topshiriqlarga boʻlinadi. Keyin 
ushbu vazifalar rekursiv chaqiruv yordamida yoki toʻgʻridan-toʻgʻri 
ularning hajmi yetarlicha kichik boʻlsa hal qilinadi. Nihoyat, ularning 
yechimlari birlashtirilib, asl muammoning echimi olinadi. 
Algoritmning bajarilishi.
Saralash muammosini hal qilish uchun 
uch bosqich quyidagicha boʻladi: 
1.
Saralanadigan massiv taxminan bir xil oʻlchamdagi ikki qismga 
boʻlinadi; 
2.
Olingan qismlarning har biri alohida saralanadi (masalan, xuddi 
shu algoritm boʻyicha saralanadi); 
3. Yarim kattalikdagi ikkita saralangan massivlar birlashtiriladi. 
Bu eng mashhur saralash algoritmlaridan biri boʻlib, rekursiv 
algoritmlarni yaratishda ishonchni rivojlantirishning ajoyib usuli 
hisoblanadi. 
“Boʻlib tashla va hukmronlik qil” strategiyasi. 
―Boʻlib tashla va 
hukmronlik qil‖ strategiyasi yordamida muammoni qismiy jarayonlarga 
ajratamiz. Har bir kichik topshiriq uchun yechimga ega boʻlsak, pastki 
vazifalarni yechish uchun pastki vazifalardan olingan natijalarni 
"birlashtiramiz". 
Aytaylik, biz A massivni saralashni xohladik. Kichik vazifa bu p 
indeksidan boshlanib, r indeksida tugagan, A [p..r] bilan belgilangan 
kichik qismini ajratishdir. 
“Boʻlib tashlash”. 
Agar q qiymati p va r orasida boʻlsa, biz A 
[p..r] massivni ikkita A [p..q] va A [q + 1, r] kichik massivlarga 
boʻlishimiz mumkin. 

Download 4,61 Mb.