Posted on by Sherzod Shermukhamedov

Tartiblash. Mergesort

Mergesort

Mergesort effektiv tartiblash algoritmlaridan biri bo’lib uning ishlash prinsipi «bo’lib tashla va hukmronlik qil» (divide and conquer) tamoyiliga asoslanadi. U tartiblash jarayonida ro’yhatni (array’ni) ikkiga bo’ladi, ikki tarafini yana ikkiga bo’ladi, ikki tarafini yana ikkiga bo’ladi, … ikki tarafda bitta son (yoki bir tarafda bitta son) qolguncha bo’lishda davom etadi. Keyin ularni tartiblashni boshlaydi. Bittalik yonma-yon turgan sonlar tartiblanib bo’lingach, ularni array sifatida birlashtiriladi. Birlashtirilgan, yonma-yon turgan ikkita elementli array’lar o’zaro tartiblanadi va birlashtiriladi. Keyin to’rtta elementli arraylar o’zaro tartiblanib birlashtiriladi. Shu tariqa bo’laklar bitta butun array’ga yig’ilguncha davom etadi.

Mergesort’ning effektivligi – uning ishlash vaqtida, time complexity – O(n log n). Insertion sort va Selection sort bilan solishtirganda, ishlash vaqti ancha samarali.

Ishlash prinsipi

Mergesort vizualizatsiyasi
Mergesortning ishlash prinsipi. Image credit: https://link.medium.com/xxbF3brb09
Mergesort ishlash prinsipi
Mergesortning ishlash prinsipi. Image credit: https://link.medium.com/xxbF3brb09

Kod

Mergesort’ni tushunib olish biroz murakkabroq.
Kodda izohlar yozib chiqdim, agar tushunarsiz joylari uchrasa Chrome’da Developer Tools’ni ochib, Console tab’da quyidagi kodni ishga tushirishingiz mumkin. Tushunarsiz joylariga console.log() qo’yib tekshirasiz.

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/mergesort.js

Rekursiv funksiyani tushunishga qiynalsangiz, iterativ varianti ham bor:

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/mergesort-bottom-up.js

* * *

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