Tartiblash. Insertion sort

Insertion sort

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

  1. Arrayning ikkinchi elementini birinchi elementi bilan solishtiramiz. Agar ikkinchi element katta bo’lsa, birinchi element va ikkinchi element o’rnini almashtiramiz.
  2. 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.
  3. 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:

Insertion sort
Insertion sort

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.

Do'stlaringiz bilan bo'lishing!