16.2 Tanlash(Selection) orqali saralash algoritmi. Selection sort g’oyasi
Selection sort g’oyasi juda ham oddiy: har qadamda arrayning saralanmagan qismidagi eng kichik (yoki eng katta) elementni topib saralangan qism oxiriga qo’shib ketish.
Algoritm qadamlari
Yuqorida aytganimizdek arrayda ikkita qism saralanmagan va saralangan qism bo’ladi. Algoritm boshida array butunligicha saralanmagan qismda bo’ladi va algoritm oxirida esa saralangan qismga o’tadi.
Array boshidan yurib chiqamiz.
Har bir qadamda saralanmagan qismdagi eng kichik elementni topib uni saralanmagan qism boshidagi element bilan almashtiramiz.
Saralangan qismni ko’rsatkichini bittaga oshiramiz.
Oxirgi element avtomatik tarzda o’z joyida bo’lib qoladi.
Algoritm murakkabligi
Selection sort eng oddiy saralash algoritmlaridan bo’lib O(n²) vaqt tezligida ishlaydi. Ya’ni, algoritm barcha elementlarni ko’rib chiqish (n-1) mobaynida, har bir qadamda eng kichik elementni topish uchun qolgan elementlarni ko’rib chiqishi kerak bo’ladi. Matematik ko’rinishda quyidagicha bo’ladi:
17.1 Evklid algoritmi Evklid algoritmi - ikki sonni eng katta umumiy bo'luvchisini(EKUB) topib beruvchi effektiv algoritm hisoblanadi. Algoritm yunon matematiki Evklid nomiga berilgan. U bu algoritmni eramizidan 3 asr oldin o'ylab topgan. Evklid algoritmi ikkita musbat son uchun yangi juftlikni hosil qiladi, kattasini kichginasi orqali kamaytirib. Bu jarayon ikkala son teng bo'lib qolmaguncha davom ettiriladi.
Misol tariqasinda (12,14) juftligini olaylik. Dastlab 12 ni 14 olib tashlaymiz. Hosil bo'lgan juftlik - (12,2). Keyin shu jarayon taqrorlanadi:
EKUB(12,2)=EKUB(10,2)=EKUB(8,2)=EKUB(6,2)=EKUB(4,2)=EKUB(2,2)=2. Shunday qilib javob - 2. Bu algoritmini to'g'riligiga sabab agarda d=EKUB(a,b) bo'lsa demak ikki sonni ayirmasi ham d soniga bo'linadi. Ya'ni (a−b)=0(mod d).
Afsuski, bu algoritm agarda birorta son kichik bo'lib, boshqasi katta bo'lsa juda ko'p amal bajarishiga to'g'ri keladi. Masalan (2,10000001) juftligi uchun 5000000 amal bajariladi EKUBi birligini aniqlash uchun. Ya'ni eng yomon holatda algoritm O(max(a,b)) amal bajarishiga to'g'ri keladi. Buni yanada tez ishlaydigan qilish mumkin. Gap shundaki har safar katta son kichkinasidan max(a,b)/min(a,b) challi ayrilib tashlanadi. Ayirish o'rninga qoldiq olish amalini bajarish mumkin. Shunda har safar katta son kichginadan kichiklashadi. Har safar ikkala sondan bittasi kamida 2 baravar kichraygani uchun ishlash vahti O(log(min(a,b))) tashkil qiladi.
