3. Selection sort saralash algaritmi 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(n2) , bu yerda n saralaniyotgan massivning elementlar sonini bildiradi.
Massiv elementlarini tanlash usuli bilan saralashda, massivning dastlabki n-1 (n – bu masssiv elementlari sonini bildiradi) ta elementini qolgan elementlar bilan taqqoslab chiqadi songra, agarda massivning dastlabki elementlari undan keyin turgan elementdan katta bo’lsa ikkala element o’rnini almashtirib qo’yadi. Bu jarayonni oson tushunish uchun quyidagi massiv elementlarida tekshirib ko’ramiz.
Bizga quyidagicha masssiv elementlari berilgan bo’lsin:
Uning birinchi elementini qolgan elmentlari bilan taqqoslab chiqamiz:
Agar belgilangan massiv a[i] ( bu yerda i=0 ) elementi bilan undan keyin turgan ixtiyoriy a[j] ( j>i ) element a[i]>a[j] shartni qanoatlantirsa t ga j qiymatlanadi va ikkala massiv elementlari o’rni almashadi:
Keying qadamlarda xuddi yuqoridagi jarayon takrorlanadi. Faqat har safar i ning qiymati oshib boradi. Ya’ni quyidagicha:
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:
XULOSA Xulosa qilib shuni aytishim mumkinki, bu mavzuda men massiv elementlarini saralash usullarining ichida quicksort ya’ni tez saralash algoritmining qaysidir sohalarda boshqa usullarga nisbatan qulaylik tomonlari bilan ajralib turishini ko`rsatishga harakat qildim. Bundan tashqari, ya’ni quicksort algoritmidan tashqari saralash algoritmlaridan bubble sort saralash algoritmi, insertion sort saralash algoritmlarini tushuntirishga harakat qildim. Ushbu saralash algoritmlarining dasturlarini c++ tilida yozganligim uchun bu saralash algoritmlariga yanada ko`proq ko`nikma hosil qildim.
Hali sanashni bilmay turib sonlar ustida arifmetik amallar bajarib bo`lmaganidek, men ham ushbu kurs ishidagi asosiy qismning birinchi bo`limida massivlar haqida kengroq to`xtalib o`tdim. Ikkinchi bo`limda esa saralsh algoritmlarining turlari va ularning bir - biridan farqi haqida kengroq tushunchalar keltirib o`tdim. Va nihoyat uchinchi bo`limda kurs ishining asosiy qismini, quick sort saralash algoritmi va uning dasturini yozdim.
