Saralash algaritmlari va ularning taxlili C#
![Faraz qilaylik taqqoslashlar soni C ga o’rinlashtirishlar soni M
bo’lsin. Agar massiv elementlarini kamayish tartibida bo’lsa,u holda
taqqoslashlar soni eng katta bo’ladi.U ,C ga teng bo’ladi,ya’ni
o’rinlashtirishlar soni esa M ga teng bo’ladi.Agar berilgan massiv
o’shish tartibida saralangan bo’lsa,u holda taqqoslashlar va
o’rinlashtirishlar soni eng kichik bo’ladi.
8
2.2.Saralash algaritmlarining turlari.
Bunday usul karta o’yinida keng qo’llaniladi.Elementar(kartalar)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’yiladi.
To’g’ridan-to’g’ri qo’shish orqali saralash algaritmi quyidagicha
bo’ladi: {
for (int i=1;i<=x)
x=a[i];
x ni a[0] a[1] oraliqning mos joyiga qo’yish
}
Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay
bo’ladi.2-elementdan boshlab har bir elementni qarab chiqamiz,ya’ni har
bir element o’zidan oldingi turgan element bilan solishtiriladi, agar
qaralayotgan element kichik bo’lsa, oldinda turgan element bilan](https://docx.uz/documents/5099e5ff-37d8-421d-bfaa-592d1c2e1cd4/page_9.png?v=1)
![solishtiriladi,jarayon shu kabi davom etadi.Bu jarayon quyidagi
shartlarni birortasi bajarilganda to’xtatiladi;
1. x elementni oldida uning kalitidan kichik kalitli a(j) element
chiqqanda. 2. x elementni oldida element qolmaganda.
For (int i=1;i=x);
while(a[j]);
9
int t=a[j-1];
a[j-1]=a[j];
a[j]=t;
j=j-1;
}
}
Tanlash orqali saralash algaritmi.
Mazkur usul quyidagi tamoyillarga asoslangan:
1.Eng kichik kalitga ega element tanlanadi.
2.Ushbu element birinchi element bilan o’rin almashinadi.
3.Keyin mazkur jarayon qolgan n-1,n-2 element bilan takrorlanib ,to
bitta eng ‘katta’ element qolguncha davom ettiriladi.
{
for(int i=0;i<="" i="">
for( int j=i+1;j<="" i="">](https://docx.uz/documents/5099e5ff-37d8-421d-bfaa-592d1c2e1cd4/page_10.png?v=1)
![if (a[i] > a[j])
int k = a[j];
a[j]= a[i];
a[i]= k;
}
10
Algarim samaradorligi:
*Taqqoslashlar soni:
S=N(N-1)/2=(N2-N)/2
*Massiv tartiblanganda o’rinlashtirishlar soni:
Mmin=3(N-1);
*Massiv teskari tartiblanganda o’rinlashtirishlar soni:
Mmin=MminN/2=3N(N-1)/2;
Ushbu usul bo’yicha saralash bajarilsa eng yomon holda taqqoslashlar
va o’rinlashtirishlar soni tartibi n2 bo’ladi.
Pufaksimon saralash algaritmi.
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 ularning
o’rni almashtiriladi.(1-rasm).
Misol:massiv-4,3,7,2,1,6.](https://docx.uz/documents/5099e5ff-37d8-421d-bfaa-592d1c2e1cd4/page_11.png?v=1)
![2)Amalga oshirish soda;
3)Qo’shimcha o’zgaruvchilar shart emas.
Kamchiliklari:
1)Katta massivlarni uzoq qayta ishlaydi;
2)Har qanday holatda ham o’tishlar soni kamaymaydi;
“Pufaksimon” usulni yaxshilash.
1)Agar massivda o’tishlar nafaqat yuqoridan pastga,balki bir vaqtning
12
o’zida pastdan yuqoriga ham bo’lsa,u holda “yengil”elemntlar “yuqoriga
suzib” chiqadi va “og’ir” elementlar esa cho’kadi.
2)Massivda “bekor” o’tishni yo’q qilish uchun tashqi siklda massiv
saralanganligini tekshiruvchi belgi qo’yish lozim.
for (int i=0; i<=“x”);
for (int j=n-1;j>i;j--);
if (a[j]<a[j-1]);
int x=a[j-1];
a[j-1]=a[j];
a[j]=x;
O’rinlashtirish va taqqoslashlar soni:|(n*logn).
Quicksort-tez saralash algaritmi.
Bu algaritm “bo’lib ol va egalik qil” tamoyillarining yaqqol misolidir.Bu
algaritm rekursiv bo’lib,o’rtacha N*log2N ta solishtirish natijasida](https://docx.uz/documents/5099e5ff-37d8-421d-bfaa-592d1c2e1cd4/page_13.png?v=1)
![table x=a[(first+last)/2];
do{
while(a[i].FIO<x.FIO) i++;
while (a[j].FIO>x.FIO) j--;
if (i<=j)
{
If (i<j)
{
swap(a[i],a[j]; q++;
}
15
i++;
j--;
}
}
while(i<=j);
if(i<last);
qs(a,i,last);
if (first<j)
qs(a,first,j);
}
Int main(int args,char *argv[])
{
Int n;
cout <<”n=;
cin >>n;](https://docx.uz/documents/5099e5ff-37d8-421d-bfaa-592d1c2e1cd4/page_16.png?v=1)
![table talaba[n];
for (int i=0;i);
talaba[i]. t=i+1;
cin>>talaba[i].FIO;
}
qs(talaba,0,n-1);
for(int i=0;1);
cout<
cout<<”quicksort algaritmi”<
}
16
Dastur natijasi:
talabalar sonini kiriting=5
5 ta talabalar FIO sini kiriting:
Farhod
Asror
Sobir
Bobur
Vali
| 1 | Farhod |
| 2 | Asror |
| 3 | Sobir |
| 4 | Bobur |](https://docx.uz/documents/5099e5ff-37d8-421d-bfaa-592d1c2e1cd4/page_17.png?v=1)
Saralash algaritmlari va ularning taxlili C#