Selection sort (Tanlab saralash)
“Algoritm — bu dasturchilar o’zlari nima qilayotganliklarini boshqalar bilmasligini xohlagan paytida ishlatadigan so’zlari” — Unanonymous.
VIII bo’lim. 1-dars
O’tgan darsimizda sizlar bilan saralash bo’limi haqida gaplashishni va turli xil saralash algoritmlari qanday holatlarda ishlatilishi haqida qisqacha gaplashgandik.
Bugungi darsimizda sizlar bilan saralash algoritmlari ichidagi eng soddalaridan biri bo’lgan tanlab saralash (selection sort) haqida gaplashamiz.
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.
Bu jarayonni vizual qanday bo’lishini ham ko’rishingiz mumkin:
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:
Bu narsa esa soddalashgan holda O(n²) ga teng bo’lishi haqida gaplashib o’tgandik.
Algoritm implementatsiyasiga o’zingiz mustaqil urinib ko’ring.
Ushbu video darsimizda selection sort algoritmi implementatsiyasini ko’rib chiqqanmiz.
Maqolani sizga yoqqan bo’lsa unga qarsak (clap) chalib qo’yishni esdan chiqarmang. 50 tagacha qarsak chalish mumkin. Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing! Bizning Telegram va YouTube kanallarimizga, hamda Mediumdagi sahifamizga obuna bo’lishni unutmang.
Muallif: Qudratxo’ja Musayev
Manba: @AlgorithmUz telegram kanali
YouTube kanalimiz: Algorithms Uzbekistan
“Eng yaxshi reklama — bu mamnun mijoz tomonidan qilingan reklama” — Philip Kotler
