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»

Quicksort ishlash tartibi 
Shuffle. Quicksort’da tartiblashni boshlashdan avval array aralashtirib 
(!) olinadi. 
Partition. Keyin array ikkiga ajratiladi. Bunda ajratuvchi elementning (pivot) chap tarafida 
elementdan kichik qiymatlar, o’ng tarafida elementdan katta qiymatlar o’rin olishi kerak. 
Sort. So’nggi bosqichda ikki qism tartiblanadi. 
Partition va sort rekursiya ichida ishlaydi. 
Birinchi qadam – aralashtirish haqida 
bu yerda
; keyingi qadamlar – partition (ajratish) va sort 
qanday ishlashi haqida batafil tushuntirishga harakat qilaman. 

---

Partition va sort 
Aralashtirilgan array: 
[5, 0, 10, 14, 9, 7, 12, 11, 2, 4, 1, 3, 6, 8, 13] 
Ajratuvchi element – pivot‘ni tanlaymiz. Biz arrayni aralashtirganimiz uchun birinchi 
elementning qiymati arraydagi eng katta yoki eng kichik bo’lish ehtimoli kam. Shu sababli 
arrayning birinchi elementi indeksini pivot deb olamiz. Demak array uchun pivot = 0. 
Ikki pointerni (elementning indeks nomerini) belgilaymiz. Birinchi pointer i = 1, ikkinchi pointer 
– j = array.length – 1 = 14. 
i >= j bo’lmaguncha katta siklni (O) ishga tushiramiz. 
(a) Kichkina sikl ichida arr[pivot] > arr[i] shart bajarilishdan to’xtaguncha yoki i arrayning ohirgi 
elementi indeksiga teng bo’lmaguncha i ni oshirib boramiz. 
(b) Yana bir alohida kichkina sikl ichida arr[pivot] < arr[j] shart bajarilishdan to’xtaguncha yoki 
j array’ning birinchi elementi indeksiga teng bo’lmaguncha j ni oshirib boramiz. 
(a) va (b) sikllar alohida-alohida (parallel) ishlaydi. Bizning holatda i = 2 va j = 11 da kichkina 
sikllar to’xtaydi: 
[5, 0, 10, 14, 9, 7, 12, 11, 2, 4, 1, 3, 6, 8, 13] 
Sababi arr[pivot] arr[i] dan kichkina bo’lib qoldi va arr[pivot] arr[j] dan katta bo’lib qoldi. arr[i] va 
arr[j] o’rnini almashtiramiz: 
[5, 0, 3, 14, 9, 7, 12, 11, 2, 4, 1, 10, 6, 8, 13] 
(O) katta sikl ishlashda davom etadi. Biz (a) va (b) sikllarni qayta ishga tushiramiz. Kichkina 
sikllar i = 3 va j = 10 holatda to’xtaydi. 
[5, 0, 3, 14, 9, 7, 12, 11, 2, 4, 1, 10, 6, 8, 13] 
Sababi ma’lum, arr[pivot] < arr[i] va arr[pivot] > arr[j] bo’lib qoldi. arr[i] va arr[j] o’rnini 
almashtiramiz: 
[5, 0, 3, 1, 9, 7, 12, 11, 2, 4, 14, 10, 6, 8, 13] 
(O) katta sikl ishlashda davom etadi. Biz (a) va (b) sikllarni qayta ishga tushiramiz. Kichkina 
sikllar i = 4 va j = 9 holatda to’xtaydi. 
[5, 0, 3, 1, 9, 7, 12, 11, 2, 4, 14, 10, 6, 8, 13] 
arr[i] va arr[j] o’rnini almashtiramiz: 

---

[5, 0, 3, 1, 4, 7, 12, 11, 2, 9, 14, 10, 6, 8, 13] 
(O) katta sikl ishlashda davom etadi. Biz (a) va (b) sikllarni qayta ishga tushiramiz. Kichkina 
sikllar i = 5 va j = 8 holatda to’xtaydi. 
[5, 0, 3, 1, 4, 7, 12, 11, 2, 9, 14, 10, 6, 8, 13] 
arr[i] va arr[j] o’rnini almashtiramiz: 
[5, 0, 3, 1, 4, 2, 12, 11, 7, 9, 14, 10, 6, 8, 13] 
Endi esa i = 6, j = 5 bo’lib qoldi, ya’ni i j dan katta bo’lib ketdi. Bu degani biz array o’rtasini 
topdik. (O) katta siklni to’xtatamiz. Endi arr[pivot] va arr[j] o’rnini almashtiramiz. 
[2, 0, 3, 1, 4, 5, 12, 11, 7, 9, 14, 10, 6, 8, 13] 
Pivot elementni arrayning kerakli joyiga qo’ydik. Endi pivotning o’ng tarafida undan kichik 
sonlar, chap tarafida undan katta sonlar joylashdi. 
Arrayni pivot bo’yicha ikki qismini alohida-alohida tartiblaymiz. Bizning misolda array 
[2, 0, 3, 1, 4] 
va 
[12, 11, 7, 9, 14, 10, 6, 8, 13] 
ga bo’lindi. Aslida array o’zi bo’linmadi, biz arrayning qismlarini alohida tartiblaymiz. 
Birinchi qism 
[2, 0, 3, 1, 4, ...] 
pivot = 0, ya’ni arr[pivot] = 2. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga 
tushiramiz. Kichik sikllar i = 2, j = 3 holatda to’xtaydi. arr[i] va arr[j] elementlarning o’rnini 
almashtiramiz. 
[2, 0, 1, 3, 4, ...] 
Keyingi kichik sikllarda i = 3, j = 2 holatda to’xtaydi. i > j, demak katta siklni to’xtatamiz va 
arr[pivot] hamda arr[j] o’rnini almashtiramiz. 
[1, 0, 2, 3, 4, ...] 
pivot elementning chap tarafida o’zidan kichkina, o’ng tarafida o’zidan katta elementlar 
joylashdi. arrayning birinchi qismini pivot bo’yicha yana ikki ajratamiz va ularni alohida-
alohida tartiblaymiz: 

---

[0, 1, ...] 
[..., 3, 4, ...] 
Shunda birinchi qism tartiblanib bo’lgach, array’ning birinchi pivotdan chap qismi tartiblandi: 
[0, 1, 2, 3, 4, 5, 12, 11, 7, 9, 14, 10, 6, 8, 13] 
Ikkinchi qism 
[..., 12, 11, 7, 9, 14, 10, 6, 8, 13] 
pivot = 0, ya’ni arr[pivot] = 12. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga 
tushiramiz. Bunda i = 6, j = 14 dan boshlanadi. Kichik sikllar i = 10, j = 13 holatda to’xtaydi. 
arr[i] va arr[j] elementlarning o’rnini almashtiramiz. 
[..., 12, 11, 7, 9, 8, 10, 6, 14, 13] 
(O) katta sikl ishlashda davom etadi. Biz (a) va (b) sikllarni qayta ishga tushiramiz. Kichkina 
sikllar i = 13 va j = 12 holatda to’xtaydi. i > j bo’lgani uchun katta sikl ham to’xtaydi. arr[pivot] 
va arr[j] o’rnini almashtiramiz. 
[..., 6, 11, 7, 9, 8, 10, 12, 14, 13] 
pivot element (12) ning chap tarafida o’zidan kichik elementlar, o’ng tarafida o’zidan katta 
elementlar joylashdi. Endi pivot bo’yicha yana kichkina qismlarga ajratib, ularni alohida-
alohida tartiblaymiz. 
2.1 qism 
[..., 6, 11, 7, 9, 8, 10, ...] 
2.2 qism 
[..., 14, 13] 
2.1 qismni tartiblashni davom ettiramiz. 
2.1 qismda pivot = 6, ya’ni array’ning 6-elementi. Yuqoridagi kabi katta (O) va kichik (a)