Tartiblash. Selection sort

Selection sort – iteratsiya ichida array elementlarini ko’rib chiqib, eng kichkinasini topish va uni arrayning tartiblangan qismiga qo’shishdan iborat.

Selection sort’ning ustunliklari:

• Oddiy algoritm
• Kichik array’lar uchun mos

Kamchiliklari:

• Katta array’larda mahsuldorlik pasayib ketadi, sababi juda ko’p solishtirishlarni amalga oshirish kerak bo’ladi.
• Upper bound va Lower bound bir xil – O(N²). Ya’ni tartiblangan arrayni ham ohirigacha tekshirib chiqadi. Algoritm mergesort va quicksort bilan solishtirganda yaxshi natija bermaydi. Kodni optimizatsiya qilish mumkin, ammo bu ishlash vaqtiga katta ta’sir ko’rsatmaydi.

Ishlash konsepti

1. Arrayning birinchi elementini ikkinchi elementdan boshlab ohirgi elementgacha solishtirib chiqadi. Agar ular orasida birinchi elementdan kichkina qiymatdagi element (minimum) chiqsa, birinchi element va minimumning o’rnini almashtiradi.
2. Arrayning ikkinchi elementini uchinchi elementdan boshlab ohirgi elementgacha solishtirib chiqadi. Agar ular orasida ikkinchi elementdan kichkina qiymatdagi element (minimum) chiqsa, ikkinchi element va minimumning o’rnini almashtiradi.
3. Arrayning uchinchi elementini to’rtinchi elementdan boshlab ohirgi elementgacha solishtirib chiqadi. Agar ular orasida uchinchi elementdan kichkina qiymatdagi element (minimum) chiqsa, uchinchi element va minimumning o’rnini almashtiradi.

Shu tariqa array ohirigacha solishtiruv amalga oshadi.

Ishlash tartibini quyidagi gif’da tushunib olishingiz mumkin:

Kod:

Note: Funksiya faqat integer sonlarni to’g’ri tartiblaydi. Harflarni yoki string sonlarni to’g’ri tartiblash uchun «>» dan boshqa amalni ishlatish kerak. Masalan, ES6 uchun String.prototype.localeCompare() ni ishlatib ko’ring.

Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sorts/selection-sort.js

* * *

Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.