WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Tartiblaş. Selection sort

selection sort

Selection sort - iteratsiya içida array elementlarini körib çiqib, eng kiçkinasini topiş va uni arrayning tartiblangan qismiga qöşişdan iborat.

Selection sort'ning ustunliklari:

  • Oddiy algoritm
  • Kiçik array'lar uçun mos

Kamçiliklari:

  • Katta array'larda mahsuldorlik pasayib ketadi, sababi juda köp soliştirişlarni amalga oşiriş kerak böladi.
  • Upper bound va Lower bound bir xil - O(N2). Ya'ni tartiblangan arrayni ham ohirigaça tekşirib çiqadi. Algoritm mergesort va quicksort bilan soliştirganda yaxşi natija bermaydi. Kodni optimizatsiya qiliş mumkin, ammo bu işlaş vaqtiga katta ta'sir körsatmaydi.

Işlaş konsepti

  1. Arrayning birinçi elementini ikkinçi elementdan boşlab ohirgi elementgaça soliştirib çiqadi. Agar ular orasida birinçi elementdan kiçkina qiymatdagi element (minimum) çiqsa, birinçi element va minimumning örnini almaştiradi.
  2. Arrayning ikkinçi elementini uçinçi elementdan boşlab ohirgi elementgaça soliştirib çiqadi. Agar ular orasida ikkinçi elementdan kiçkina qiymatdagi element (minimum) çiqsa, ikkinçi element va minimumning örnini almaştiradi.
  3. Arrayning uçinçi elementini törtinçi elementdan boşlab ohirgi elementgaça soliştirib çiqadi. Agar ular orasida uçinçi elementdan kiçkina qiymatdagi element (minimum) çiqsa, uçinçi element va minimumning örnini almaştiradi.

Şu tariqa array ohirigaça soliştiruv amalga oşadi.

Işlaş tartibini quyidagi gif'da tuşunib olişingiz mumkin:

Selection sort Selection sort. Image credit: https://link.medium.com/eixWickfQ9

Kod:

*Note: Funksiya faqat integer sonlarni töğri tartiblaydi. Harflarni yoki string sonlarni töğri tartiblaş uçun ">" dan boşqa amalni işlatiş kerak. Masalan, ES6 uçun *String.prototype.localeCompare() ni işlatib köring.

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


Mavzu böyiça savollarni Github'dagi Webmaxor / leetcode-solutions repository'da yozişingiz yoki kodda **Reference in new issue **ni bosib, qoldirişingiz mumkin.