WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Tartiblaş. Quicksort

Sorting

Quicksort yigirmançi asrning eng muhim algoritmlaridan bölib, u köp dasturlarda işlatiladi. Mergesort kabi, Quicksort ham rekursiv algoritm, lekin Quicksort'ning Mergesort'dan farqi - rekursiya iş tugallangaç işga tuşadi (Mergesort'da avval rekursiya, keyin iş boşlanardi).

Quicksort işlaş tartibi

Şuffle. Quicksort'da tartiblaşni boşlaşdan avval array aralaştirib (!) olinadi.

Mavzu: Aralaştiriş haqida

**Partition. **Keyin array ikkiga ajratiladi. Bunda ajratuvçi elementning (pivot) çap tarafida elementdan kiçik qiymatlar, öng tarafida elementdan katta qiymatlar örin olişi kerak.

**Sort. **Sönggi bosqiçda ikki qism tartiblanadi.

Partition va sort rekursiya içida işlaydi.

Birinçi qadam - aralaştiriş haqida bu yerda; keyingi qadamlar - partition (ajratiş) va sort qanday işlaşi haqida batafil tuşuntirişga harakat qilaman.

Partition va sort

Aralaştirilgan array:

[5, 0, 10, 14, 9, 7, 12, 11, 2, 4, 1, 3, 6, 8, 13]

Ajratuvçi element - pivot'ni tanlaymiz. Biz arrayni aralaştirganimiz uçun birinçi elementning qiymati arraydagi eng katta yoki eng kiçik böliş ehtimoli kam. Şu sababli arrayning birinçi elementi indeksini pivot deb olamiz. Demak array uçun pivot = 0.

Ikki pointerni (elementning indeks nomerini) belgilaymiz. Birinçi pointer i = 1, ikkinçi pointer - j = array.length - 1 = 14.

i >= j bölmagunça katta siklni (O) işga tuşiramiz.

(a) Kiçkina sikl içida arr[pivot] > arr[i] şart bajarilişdan töxtagunça yoki i arrayning ohirgi elementi indeksiga teng bölmagunça i ni oşirib boramiz.

(b) Yana bir alohida kiçkina sikl içida arr[pivot] < arr[j] şart bajarilişdan töxtagunça yoki j array'ning birinçi elementi indeksiga teng bölmagunça j ni oşirib boramiz.

**(a) **va (b) sikllar alohida-alohida (parallel) işlaydi. Bizning holatda i = 2 va j = 11 da kiçkina sikllar töxtaydi:

[5, 0, 10, 14, 9, 7, 12, 11, 2, 4, 1, 3, 6, 8, 13]

Sababi arr[pivot] arr[i] dan kiçkina bölib qoldi va arr[pivot] arr[j] dan katta bölib qoldi. arr[i] va arr[j] örnini almaştiramiz:

[5, 0, 3, 14, 9, 7, 12, 11, 2, 4, 1, 10, 6, 8, 13]

(O) katta sikl işlaşda davom etadi. Biz (a) va (b) sikllarni qayta işga tuşiramiz. Kiçkina sikllar i = 3 va j = 10 holatda tö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] bölib qoldi. arr[i] va arr[j] örnini almaştiramiz:

[5, 0, 3, 1, 9, 7, 12, 11, 2, 4, 14, 10, 6, 8, 13]

(O) katta sikl işlaşda davom etadi. Biz (a) va (b) sikllarni qayta işga tuşiramiz. Kiçkina sikllar i = 4 va j = 9 holatda töxtaydi.

[5, 0, 3, 1, 9, 7, 12, 11, 2, 4, 14, 10, 6, 8, 13]

arr[i] va arr[j] örnini almaştiramiz:

[5, 0, 3, 1, 4, 7, 12, 11, 2, 9, 14, 10, 6, 8, 13]

(O) katta sikl işlaşda davom etadi. Biz (a) va (b) sikllarni qayta işga tuşiramiz. Kiçkina sikllar i = 5 va j = 8 holatda töxtaydi.

[5, 0, 3, 1, 4, 7, 12, 11, 2, 9, 14, 10, 6, 8, 13]

arr[i] va arr[j] örnini almaştiramiz:

[5, 0, 3, 1, 4, 2, 12, 11, 7, 9, 14, 10, 6, 8, 13]

Endi esa i = 6, j = 5 bölib qoldi, ya'ni i j dan katta bölib ketdi. Bu degani biz array örtasini topdik. (O) katta siklni töxtatamiz. Endi arr[pivot] va arr[j] örnini almaştiramiz.

[2, 0, 3, 1, 4, 5, 12, 11, 7, 9, 14, 10, 6, 8, 13]

Pivot elementni arrayning kerakli joyiga qöydik. Endi pivotning öng tarafida undan kiçik sonlar, çap tarafida undan katta sonlar joylaşdi.

Arrayni pivot böyiça ikki qismini alohida-alohida tartiblaymiz. Bizning misolda array

[2, 0, 3, 1, 4]

va

[12, 11, 7, 9, 14, 10, 6, 8, 13]

ga bölindi. Aslida array özi bölinmadi, biz arrayning qismlarini alohida tartiblaymiz.

Birinçi qism

[2, 0, 3, 1, 4, ...]

pivot = 0, ya'ni arr[pivot] = 2. Yuqoridagi kabi katta (O) va kiçik (a) (b) sikllarni işga tuşiramiz. Kiçik sikllar i = 2, j = 3 holatda töxtaydi. arr[i] va arr[j] elementlarning örnini almaştiramiz.

[2, 0, 1, 3, 4, ...]

Keyingi kiçik sikllarda i = 3, j = 2 holatda töxtaydi. i > j, demak katta siklni töxtatamiz va arr[pivot] hamda arr[j] örnini almaştiramiz.

[1, 0, 2, 3, 4, ...]

pivot elementning çap tarafida özidan kiçkina, öng tarafida özidan katta elementlar joylaşdi. arrayning birinçi qismini pivot böyiça yana ikki ajratamiz va ularni alohida-alohida tartiblaymiz:

[0, 1, ...]

[..., 3, 4, ...]

Şunda birinçi qism tartiblanib bölgaç, array'ning birinçi pivotdan çap qismi tartiblandi:

[0, 1, 2, 3, 4, 5, 12, 11, 7, 9, 14, 10, 6, 8, 13]

Ikkinçi qism

[..., 12, 11, 7, 9, 14, 10, 6, 8, 13]

pivot = 0, ya'ni arr[pivot] = 12. Yuqoridagi kabi katta (O) va kiçik (a) (b) sikllarni işga tuşiramiz. Bunda i = 6, j = 14 dan boşlanadi. Kiçik sikllar i = 10, j = 13 holatda töxtaydi. arr[i] va arr[j] elementlarning örnini almaştiramiz.

[..., 12, 11, 7, 9, 8, 10, 6, 14, 13]

(O) katta sikl işlaşda davom etadi. Biz (a) va (b) sikllarni qayta işga tuşiramiz. Kiçkina sikllar i = 13 va j = 12 holatda töxtaydi. i > j bölgani uçun katta sikl ham töxtaydi. arr[pivot] va arr[j] örnini almaştiramiz.

[..., 6, 11, 7, 9, 8, 10, 12, 14, 13]

pivot element (12) ning çap tarafida özidan kiçik elementlar, öng tarafida özidan katta elementlar joylaşdi. Endi pivot böyiça yana kiçkina qismlarga ajratib, ularni alohida-alohida tartiblaymiz.

2.1 qism

[..., 6, 11, 7, 9, 8, 10, ...]

2.2 qism

[..., 14, 13]

2.1 qismni tartiblaşni davom ettiramiz.

2.1 qismda pivot = 6, ya'ni array'ning 6-elementi. Yuqoridagi kabi katta (O) va kiçik (a) (b) sikllarni işga tuşiramiz. Bunda i = 7, j = 11 dan boşlanadi. Kiçik sikllar i = 7, j = 6 holatda töxtaydi. i > j, katta (O) sikl ham töxtaydi. arr[pivot] va arr[j] teng. Bu 2.1 qismda pivot eng kiçkina son bölgani uçun bu qismda özgariş bölmadi. 2.1 qismni pivot böyiça ikkiga ajratamiz. Aniqroği birinçi qismi bölmaydi, faqat ikkinçi qismi (2.1.2) böladi xolos:

[..., 11, 7, 9, 8, 10, ...]

2.1.2 qismni tartiblaşni davom ettiramiz.

2.1.2 qismda pivot = 7, ya'ni array'ning 7-elementi. Yuqoridagi kabi katta (O) va kiçik (a) (b) sikllarni işga tuşiramiz. Bunda i = 8, j = 11 dan boşlanadi. Kiçik sikllar i = 11, j = 11 holatda töxtaydi. i = j, katta (O) sikl ham töxtaydi. arr[pivot] va arr[j] örnini almaştiramiz:

[..., 10, 7, 9, 8, 11, ...]

2.1.2 qismni pivot böyiça ikkiga ajratamiz. Aniqroği ikkinçi qismi bölmaydi, faqat birinçi qismi (2.1.2.1) böladi xolos:

[..., 10, 7, 9, 8, ...]

2.1.2.1 qismni tartiblaşni davom ettiramiz.

2.1.2.1 qismda pivot = 7, ya'ni array'ning 7-elementi. Yuqoridagi kabi katta (O) va kiçik (a) (b) sikllarni işga tuşiramiz. Bunda i = 8, j = 10 dan boşlanadi. Kiçik sikllar i = 10, j = 10 holatda töxtaydi. i = j, katta (O) sikl ham töxtaydi. arr[pivot] va arr[j] örnini almaştiramiz:

[..., 8, 7, 9, 10, ...]

2.1.2.1 qismni pivot böyiça ikkiga ajratamiz. Aniqroği ikkinçi qismi bölmaydi, faqat birinçi qismi (2.1.2.1.1) böladi xolos:

[..., 8, 7, 9, ...]

2.1.2.1.1 qismni tartiblaşni davom ettiramiz.

2.1.2.1.1 qismda pivot = 7, ya'ni array'ning 7-elementi. Yuqoridagi kabi katta (O) va kiçik (a) (b) sikllarni işga tuşiramiz. Bunda i = 8, j = 9 dan boşlanadi. Kiçik sikllar i = 9, j = 8 holatda töxtaydi. i > j, katta (O) sikl ham töxtaydi. arr[pivot] va arr[j] örnini almaştiramiz:

[..., 7, 8, 9, ...]

Biz 2.1 qismni tartiblaşni tugatdik :D

[..., 6, 7, 8, 9, 10, 11, ...]

2.2. qismi da ikkita element bor, ular tartiblangaç:

[..., 13, 14]

Biz arrayning ikkinçi qismini ham tartiblaşni tugatdik.

[..., 6, 7, 8, 9, 10, 11, 12, 13, 14]

Şunda tartiblaş yakunlangaç, array

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

tartiblandi.

Nimaga tartiblaşdan avval aralaştiriş kerak?

Yuqorida e'tibor bergan bölsangiz, 2.1, 2.1.2, 2.1.2.1 qismlarda biz pivot böyiça array'ni ikkiga böla olmadik. Sababi pivot eng kiçik (eng katta) element bölib qoldi.

Aralaştirişdan maqsad esa tanlanadigan pivot iloji boriça eng kiçik (eng katta) element bölib qolmasligining oldini oliş uçundir. Demak agar array yaxşi aralaşmagan bölsa, bizda ikkiga böliş (partition) effektiv çiqmaydi. Quicksort maksimum darajada aralaşgan array'lar uçun samarali işlaydi.

Quicksort'ning uning örtaça time complexity'si O(1.39*n log n), Mergesortdan 39% köproq.

Quicksortning ajoyibligi şundaki, u qöşimça array'siz, berilgan arrayning özida partition'ni amalga oşiradi va Mergesortga nisbatan kamroq almaştirişlar qiladi.

Qöşimça array işlatilsa, funksiya soddaroq (va qisqaroq) körinişda böladi, ammo bunda Quicksort'ni işlatişdan foyda yöqoladi.

Worst case - O(1/2 N2) - allaqaçon tartiblangan array uçun. Çunki bu holatda pivot array'ni ikki qismga böla olmaydi. Nima uçun arrayni aralaştiriş (şuffle) muhim ekanligini tuşungan bölsangiz kerak ;)

Kod

Note: Funksiya faqat integer sonlarni töğri tartiblaydi. Harflarni yoki string sonlarni töğri tartiblaş uçun «>» dan boşqa amalni işlatiş kerak. Masalan, ES6 uçun String.prototype.localeCompare() ni işlatib köring.

Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sorts/quicksort.js

Quicksort'ning qisqa körinişi

Qisqa körinişda array qismlari left va right array'larga yiğiladi (qöşimça array işlatiladi). Ammo kodi öqib, eslab qolişga oson böladi.

Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sorts/quicksort-concise.js


Mavzu böyiça savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozişingiz yoki kodda **Reference in new issue **ni bosib, qoldirişingiz mumkin.