Saralash haqida. Saralash usullari va ularning turlari. Bubble Sort saralash algoritmi va uning dasturi

Insertion sort
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.
#include
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; }
Dastur natijasi quyidagicha:

3. Quick sort
Quicksort saralash algoritmi bu tezkor saralash degan ma’noni anglatadi. Tezkor saralash ( Quick sort ) algoritmi 1964 - yilda Charlz Hoar tomonidan taklif qilingan. Charliz Hoar ingliz olimi, informatika va hisoblash texnikasi sohasida yetuk mutaxassis. Uning “ Tezkor saralash ” algoritmi saralash bo`yicha eng ommabop algoritm.
Bu algoritm ham “ Bo`lib tashla va hukmronlik qil “ ( Bu metod algoritmlarni qurishning asosiy metodlaridan biri. Murakkab masalani yechish uchun uni oddiyroq bo`laklarga ajratish kerak. Massivni ham xuddi shunday saralash mumkin . buning uchun uni ikki bo`lakka ajratamiz, bo`laklarni alohida saralaymiz, saralangan massivlarni birlashtiramiz ) metodiga asoslanadi. Algoritmining g`oyasi: Massivda bo`luvchi element x dan kichik yoki teng bo`lgan elementlar joylashsin, keyin undan katta bo`lgan elementlar joylashsin. Keyin ularni alohida saralaymiz. Agar a massivda n ta element bo`lsa, bo`luvchi element sifatida x=a[n/2] ni olamiz. Chap tomondan x dan kichik katta yoki teng bo`lgan birinchi elementni topamiz, o`ng tomondan esa x dan katta bo`lmagan birinchi elementni topamiz va ikkalasining o`rnini almashtiramiz. Ana shu jarayonni bo`luvchi element x ning chap tomonida undan kichik elementlar, o`ng tomonida esa undan katta bo`lgan elementlar joylashb qolgunicha davom ettiramiz. Shundan so`ng yuqoridagi jarayonni chap tomon uchun alohida o`ng tomon uchun alohida bajaramiz va hakozo. Ko`rinib turganidek bu rekursiya jarayoniga to`g`ri keladi.
Quyida Quick sort saralash algoritmining c++ tilidagi dastur matnini keltiramiz:
#include
using namespace std;
int a[1000];
void qsort(int l, int r)
{ int m, x, j, t, i;
m=(l+r)/2;
x=a[m];
i=l; j=r;
while(i<=j){
while(a[i]while(a[j]>x) j--;
if(i<=j) {
t=a[i]; a[i]=a[j]; a[j]=t;
i++; j--;}
}
if(lif(iint main()
{ int i, n;
cin>>n;
for(i=0; icin>>a[i];
qsort(0,n-1);
for(i=0; icout << a[i] << " ";
return 0; }

Quyida tanlash asosida saralash algoritmining dastur matnini C++ dasturlash tilida keltirib o’tamiz:
#include
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 taqqoslash sharti bajarilsa taqqoslangan elementlar o’rni almashadi va bu jarayon taqqoslash sharti bajarilmay qolguncha davom etadi .
Dastur natijasi quyidagicha bo’ladi: