Guruhi talabasining

(O)
va kichik 
(a) (b)
sikllarni ishga tushiramiz. Bunda i = 8, j = 9 dan 
boshlanadi. Kichik sikllar i = 9, j = 8 holatda to’xtaydi. i > j, katta 
(O)
sikl ham 
to’xtaydi. arr[pivot] va arr[j] o’rnini almashtiramiz: 
[..., 7, 8, 9, ...] 
Biz 2.1 qismni tartiblashni tugatdik 
[..., 6, 7, 8, 9, 10, 11, ...] 
2.2. qismi da ikkita element bor, ular tartiblangach: 
[..., 13, 14] 
Biz arrayning ikkinchi qismini ham tartiblashni tugatdik. 
[..., 6, 7, 8, 9, 10, 11, 12, 13, 14] 
Shunda tartiblash yakunlangach, array 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] 
tartiblandi. 
Nimaga tartiblashdan avval aralashtirish kerak? 
Yuqorida e’tibor bergan bo’lsangiz, 2.1, 2.1.2, 2.1.2.1 qismlarda biz pivot bo’yicha 
array’ni ikkiga bo’la olmadik. Sababi pivot eng kichik (eng katta) element bo’lib 
qoldi. 
Aralashtirishdan maqsad esa tanlanadigan pivot iloji boricha eng kichik (eng katta) 
element bo’lib qolmasligining oldini olish uchundir. Demak agar array yaxshi 

---

aralashmagan bo’lsa, bizda ikkiga bo’lish (partition) effektiv 
chiqmaydi. 
Quicksort maksimum darajada aralashgan array’lar uchun 
samarali ishlaydi.
Quicksort’ning uning o’rtacha time complexity’si O(1.39*n log n), Mergesortdan 
39% ko’proq. 
Quicksortning ajoyibligi shundaki, u qo’shimcha array’siz, berilgan arrayning 
o’zida partition’ni amalga oshiradi va Mergesortga nisbatan kamroq 
almashtirishlar qiladi. 
Qo’shimcha array ishlatilsa, funksiya soddaroq (va qisqaroq) ko’rinishda bo’ladi, 
ammo bunda Quicksort’ni ishlatishdan foyda yo’qoladi. 
Worst case – O(1/2 N
2
) – allaqachon tartiblangan array uchun. Chunki bu holatda 
pivot array’ni ikki qismga bo’la olmaydi. Nima uchun arrayni aralashtirish 
(shuffle) muhim ekanligini tushungan bo’lsangiz kerak 
Kod 
 
function
quickSort
(arr) { 
function