To’g’ridan-to’g’ri tanlash usuli bilan saralash
Faraz qilaylik, a
1
, a
2
, … , 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
1
bilan o’rin almashadi.
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; i cin>>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; i cout << 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; i cin>>a[i];
for(i=0; i ; i++) {
t=i;
for(j=i+1; j if(a[t]>a[j]) {
t=j;
}
}
buf=a[t];
a[t]=a[i];
a[i]=buf;
}
for(i=0; i cout << 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:
| 