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.
