Birlashtiruv saralash. Tezkor tartiblash (quicksort). Chiziqli saralash algoritmlari. Tartiblash. Mergesort effektiv tartiblash algoritmlaridan biri bo’lib uning ishlash prinsipi «bo’lib tashla va hukmronlik qil»

---

 
Birlashtiruv saralash. Tezkor tartiblash (quicksort). Chiziqli saralash algoritmlari. 
 
Tartiblash. 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

---

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. 
function
mergeSort
(arr) { 
function
merge
(arr, aux, low, mid, high) { 
// mutatsiyaning oldini olib, arr array elementlaridan 
// aux array yasaymiz
aux 
=
[...arr] 
// i arrayning pastki qismi. mergeSort birinchi ishga tushganda
// low = 0, mid = 0, high = 1 bo'ladi.
let
i 
=
low, j 
=
mid 
+
1
// Qismlarni solishtirib, arr array'ga tartiblangan elementlarni
// yig'amiz
for
(
let
k 
=
low; k 
<=
high; k
++
) { 
if
(i 
>
mid) { 
arr[k] 
=
aux[j
++
] 
} 
else
if
(j 
>
high) { 
arr[k] 
=
aux[i
++
] 
} 
else
if
(aux[j] 
<
aux[i]) { 
arr[k] 
=
aux[j
++
] 
} 
else
{ 
arr[k] 
=
aux[i
++
] 
} 
} 
} 

---

function
sort
(arr, aux, low, high) { 
// arrayning (yoki array qismining) yuqori elementi pastki 
// elementidan kichkina bo'lsa yoki teng bo'lib qolsa rekursiv
// funksiyani to'xtatamiz
if
(high 
<=
low) { 
return
; 
} 
// arrayning (yoki array qismining) o'rtasini topamiz
const
mid 
=
low 
+
Math
.
trunc
((high 
-
low) 
/
2
) 
// arrayning (yoki array qismining ikki tarafini tartiblaymiz)
sort
(arr, aux, low, mid) 
sort
(arr, aux, mid 
+
1
, high) 
// bu qismi high <= low bo'lgan holatda, funksiya to'xtaganda
// bitta oldingi chaqirilgan sort() ichida ishlaydi.
// Batafsil - rekursiyani o'rganing.
merge
(arr, aux, low, mid, high) 
} 
let
aux 
=
[] 
sort
(arr, aux, 
0
, arr.
length
-
1
) 
return
arr 
} 
Quicksort 
yigirmanchi asrning eng muhim algoritmlaridan bo’lib, u ko’p 
dasturlarda ishlatiladi. Mergesort kabi, Quicksort ham rekursiv algoritm, lekin 
Quicksort’ning Mergesort’dan farqi – rekursiya ish tugallangach ishga tushadi 
(Mergesort’da avval rekursiya, keyin ish boshlanardi).