Selection Sort

---

Vaqt murakkabligi nima ekani haqidagi umumiy tushuntirish uchun ushbu sahifaga qarang.

---

Selection Sort’ning vaqt murakkabligi

Selection Sort algoritmi massivdagi barcha elementlarni aylanib chiqib, eng kichik qiymatni topadi va uni massiv boshiga ko‘chiradi, massiv saralanmaguncha buni qayta-qayta takrorlaydi.

Selection Sort \(n\) ta qiymatli massivni \(n-1\) marta aylanib chiqadi. Buning sababi shundaki, algoritm oxirgisidan tashqari barcha qiymatlarni saralab bo‘lganda, oxirgi qiymat ham o‘zining to‘g‘ri joyida bo‘lishi shart.

Algoritm massivni birinchi marta aylanib chiqqanda qaysi biri eng kichik ekanini aniqlash uchun barcha qiymatlar taqqoslanadi.

Algoritm massivni ikkinchi marta aylanib chiqqanda qaysi biri eng kichik ekanini aniqlash uchun birinchi qiymatdan tashqari barcha qiymatlar taqqoslanadi.

Shu tariqa massivning saralanmagan qismi saralash tugaguncha tobora qisqarib boradi. Demak, algoritm eng kichik qiymatni topib, uni massiv boshiga ko‘chirish uchun massivni aylanib chiqqanda o‘rtacha \(\frac{n}{2}\) ta element ko‘rib chiqiladi.

Kerakli barcha taqqoslashlardan tashqari, o‘rin almashtirishni ko‘rib chiqishlar soni \(n -1 \) ga teng.

Selection Sort algoritmi uchun amallar sonini hisoblashni boshlashimiz mumkin:

\[ \begin{equation} \begin{aligned} Amallar {} & = (n-1)\cdot \frac{n}{2} + (n - 1) \\ & = \frac{n^2}{2} - \frac{n}{2} + (n - 1) \\ & = \frac{n^2}{2} + \frac{n}{2} \end{aligned} \end{equation} \]

Algoritmlarning bajarilish vaqtini ko‘rib chiqayotganda juda katta ma’lumotlar to‘plamlariga qaraymiz, ya’ni \(n\) juda katta son. Juda katta \(n\) uchun esa \(\frac{n^2}{2}\) hadi \(\frac{n}{2}\) hadidan shunchalik katta bo‘ladiki, ikkinchi had \(\frac{n}{2}\) ni shunchaki olib tashlab, taqribiy hisoblashimiz mumkin.

\[Amallar = \frac{n^2}{2} + \frac{n}{2} \approx \frac{n^2}{2} = \frac{1}{2} \cdot n^2 \]

Selection Sort algoritmining vaqt murakkabligini Big O notatsiyasi yordamida tavsiflasak, quyidagini olamiz:

\[ O( \frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}} \]

Selection Sort algoritmining vaqt murakkabligini esa grafikda quyidagicha ko‘rsatish mumkin:

Ko‘rib turganingizdek, bajarilish vaqti Bubble Sort’dagi bilan bir xil: massiv hajmi oshirilganda bajarilish vaqti juda tez ortadi.

---

Selection Sort simulyatsiyasi

Massivdagi turli miqdordagi qiymatlar uchun simulyatsiyani ishga tushiring va Selection Sort \(n\) ta elementli massiv uchun bajaradigan amallar soni qanday qilib \(O(n^2)\) bo‘lishini ko‘ring:

Ushbu simulyatsiyada ko‘rishimiz mumkin bo‘lgan Bubble Sort’dan eng muhim farq shundaki, Selection Sort uchun eng yaxshi va eng yomon holatlar amalda deyarli bir xil (\(O(n^2)\)), Bubble Sort uchun esa eng yaxshi holatdagi bajarilish vaqti atigi \(O(n)\).

Selection Sort uchun eng yaxshi va eng yomon holat o‘rtasidagi farq asosan o‘rin almashtirishlar sonida. Eng yaxshi holatda Selection Sort hech bir qiymatning o‘rnini almashtirishi shart emas, chunki massiv allaqachon saralangan. Eng yomon holatda esa massiv allaqachon saralangan, ammo teskari tartibda bo‘ladi, shuning uchun Selection Sort massivdagi qiymatlar soniga teng marta o‘rin almashtirishi kerak.

---

---