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).
Quicksort ishlash tartibi
Shuffle. Quicksort’da tartiblashni boshlashdan avval array aralashtirib (!) olinadi.
Mavzu: Aralashtirish haqida
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) (b) sikllarni ishga tushiramiz. Bunda i = 7, j = 11 dan boshlanadi. Kichik sikllar i = 7, j = 6 holatda to’xtaydi. i > j, katta (O) sikl ham to’xtaydi. arr[pivot] va arr[j] teng. Bu 2.1 qismda pivot eng kichkina son bo’lgani uchun bu qismda o’zgarish bo’lmadi. 2.1 qismni pivot bo’yicha ikkiga ajratamiz. Aniqrog’i birinchi qismi bo’lmaydi, faqat ikkinchi qismi (2.1.2) bo’ladi xolos:
[..., 11, 7, 9, 8, 10, ...]
2.1.2 qismni tartiblashni davom ettiramiz.
2.1.2 qismda pivot = 7, ya’ni array’ning 7-elementi. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga tushiramiz. Bunda i = 8, j = 11 dan boshlanadi. Kichik sikllar i = 11, j = 11 holatda to’xtaydi. i = j, katta (O) sikl ham to’xtaydi. arr[pivot] va arr[j] o’rnini almashtiramiz:
[..., 10, 7, 9, 8, 11, ...]
2.1.2 qismni pivot bo’yicha ikkiga ajratamiz. Aniqrog’i ikkinchi qismi bo’lmaydi, faqat birinchi qismi (2.1.2.1) bo’ladi xolos:
[..., 10, 7, 9, 8, ...]
2.1.2.1 qismni tartiblashni davom ettiramiz.
2.1.2.1 qismda pivot = 7, ya’ni array’ning 7-elementi. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga tushiramiz. Bunda i = 8, j = 10 dan boshlanadi. Kichik sikllar i = 10, j = 10 holatda to’xtaydi. i = j, katta (O) sikl ham to’xtaydi. arr[pivot] va arr[j] o’rnini almashtiramiz:
[..., 8, 7, 9, 10, ...]
2.1.2.1 qismni pivot bo’yicha ikkiga ajratamiz. Aniqrog’i ikkinchi qismi bo’lmaydi, faqat birinchi qismi (2.1.2.1.1) bo’ladi xolos:
[..., 8, 7, 9, ...]
2.1.2.1.1 qismni tartiblashni davom ettiramiz.
2.1.2.1.1 qismda pivot = 7, ya’ni array’ning 7-elementi. Yuqoridagi kabi katta (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 N2) – 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
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/quicksort.js
Quicksort’ning qisqa ko’rinishi
Qisqa ko’rinishda array qismlari left va right array’larga yig’iladi (qo’shimcha array ishlatiladi). Ammo kodi o’qib, eslab qolishga oson bo’ladi.
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sorts/quicksort-concise.js
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.