Algoritmlar bo’yicha navbatdagi maqolalar tartiblash metodlari haqida bo’ladi. Eng oson va oddiy tartiblash algoritmlaridan biri – Insertion sort. U array elementlarini solishtirib, elementlarning o’rnini almashtirish hisobiga tartiblaydi.
Insertion sort’ning ustunliklari:
- Oddiy algoritm
- Kichik array’lar uchun mahsuldorlik yuqori
Kamchiliklari:
- Katta array’larda mahsuldorlik pasayib ketadi, sababi juda ko’p solishtirishlarni amalga oshirish kerak bo’ladi.
- Upper bound – ¼ N2 ~ O(N2). Algoritm mergesort va quicksort bilan solishtirganda yaxshi natija ko’rsatmaydi.
Ishlash konsepti
- Arrayning ikkinchi elementini birinchi elementi bilan solishtiramiz. Agar ikkinchi element katta bo’lsa, birinchi element va ikkinchi element o’rnini almashtiramiz.
- Arrayning uchinchi elementini ikkinchi elementi bilan solishtiramiz. Agar uchinchi elementi ikkinchi elementidan katta bo’lsa, uchinchi va ikkinchi element o’rnini almashtiramiz. So’ng 1-qadamni takrorlaymiz.
- Arrayning to’rtinchi elementini uchinchi elementi bilan solishtiramiz. Agar to’rtinchi elementi uchinchi elementidan katta bo’lsa, to’rtinchi va uchinchi element o’rnini almashtiramiz. So’ng 2-qadamni takrorlaymiz.
Animatsion ko’rinishda:
Kod:
Note: Funksiya faqat integer sonlarni to’g’ri tartiblaydi. Harflarni yoki string sonlarni 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/insertion-sort.js
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.