WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Dijkstra'ning uç tomonlama böliş (3-way partitioning) algoritmi

Sorting

Quicksort bilan tanişib çiqqan bölsangiz, algoritmda böluvçi element (pivot) array'ni ikkiga böladi. Bunda array[pivot]'ning çap tarafida undan kiçkina qiymatlar, öng tarafida undan katta qiymatlar örin oladi. Uşbu algoritmning kamçiligi şundaki - röyhatda bir xil qiymatlar köp uçraydigan bölsa, işlaş vaqti orta boşlaydi. Bir xil qiymatli elementlardan iborat array'ni tartiblaşda esa, Quicksort'ning time complexity'si ~ O(1/2 N2) bölib ketadi.

Algoritmni optimallaştiriş uçun array[pivot]'ga teng elementlarni tekşirişni töxtatiş tavsiya qilinadi, şunda time complexity ~ O(N lg N) gaça kamayadi. Mana şu optimallaştiriş uç tomonlama böliş (3-way partitioning) deb ataladi. 3-way partitioning algoritmining yana bir nomi - Dutç National Flag.

3-way partitioninğda maqsad, array'ni uçga şunday böliş kerakki:

  • v (v = array[pivot]) ga teng elementlar arrayning örtasida yiğilsin
  • v çegarasining (lt) çap tarafida v dan kiçkina sonlar joylaşsin
  • v çegarasining (gt) öng tarafida v dan katta sonlar joylaşsin

3-way partitioning 3-way partitioning. Image credit: Algorithms course from Coursera.

3-way partitioning algoritmi işlaş tartibi

Bizda tartiblanmagan array bor:

[6, 9, 4, 2, 8, 5, 2, 6, 5, 7, 2, 7, 6]

Boşlanğiç ma'lumotlar:

  • v sifatida Quicksort'dagidek arrayning birinçi elementi qiymatini olamiz. v = 6.
  • arrayni boşidan ohirigaça tekşirişni boşlaymiz. Sikl boşida** i = 0**.
  • v'ning çap çegarasi -** lt = 0**. array[lt] = 6, öng çegarasi - gt = array.length - 1. array[gt] = 6

Işlaş tartibi:

  • Siklni işga tuşiramiz, sikl şarti i > gt bölgunga qadar davom ettiramiz.
  • (array[i] <v): array[lt] va array[i] örnini almaştiramiz; lt va i ni bittaga oşiramiz (increment).
  • (array[i] > v): array[gt] va array[i] örnini almaştiramiz; gt ni bittaga kamaytiramiz (decrement).
  • (array[i] == v): i ni bittaga oşiramiz (increment).
  • i > gt bölganda siklni töxtatamiz.
  • array'ning v çap çegarasidan (lt) çap qismi hamda öng çegarasidan (lt) öng qismi uçun tartiblaşni qaytadan boşlaymiz (rekursiya).

1-sikl. i = 0, lt = 0, gt = 12.

array[i] = 6 == v, i++ . Array'da özgariş bölmaydi:

[6, 9, 4, 2, 8, 5, 2, 6, 5, 7, 2, 7, 6]

2-sikl. i = 1, lt = 0, gt = 12.

array[i] = 9 > v, array[gt] va array[i] örnini almaştiramiz. gt--.

[6, 6, 4, 2, 8, 5, 2, 6, 5, 7, 2, 7, 9]

3-sikl. i = 1, lt = 0, gt = 11.

array[i] = 6 == v, i++. Array'da özgariş bölmaydi.

[6, 6, 4, 2, 8, 5, 2, 6, 5, 7, 2, 7, 9]

4-sikl. i = 2, lt = 0, gt = 11.

array[i] = 4 < v. array[lt] va array[i] örni almaşadi. lt++, i++.

[4, 6, 6, 2, 8, 5, 2, 6, 5, 7, 2, 7, 9]

5-sikl. i = 3, lt = 1, gt = 11.

array[i] = 2 < v, array[lt] va array[i] örni almaşadi. lt++, i++.

[4, 2, 6, 6, 8, 5, 2, 6, 5, 7, 2, 7, 9]

6-sikl. i = 4, lt = 2, gt = 11.

array[i] = 8 > v, array[gt] va array[i] örni almaşadi. gt--.

[4, 2, 6, 6, 7, 5, 2, 6, 5, 7, 2, 8, 9]

7-sikl. i = 4, lt = 2, gt = 10.

array[i] = 7 > v, array[gt] va array[i] örni almaşadi. gt--.

[4, 2, 6, 6, 2, 5, 2, 6, 5, 7, 7, 8, 9]

8-sikl. i = 4, lt = 2, gt = 9.

array[i] = 2 < v. array[lt] va array[i] örni almaşadi. lt++, i++.

[4, 2, 2, 6, 6, 5, 2, 6, 5, 7, 7, 8, 9]

9-sikl. i = 5, lt = 3, gt = 9.

array[i] = 5 < v. array[lt] va array[i] örni almaşadi. lt++, i++.

[4, 2, 2, 5, 6, 6, 2, 6, 5, 7, 7, 8, 9]

10-sikl. i = 6, lt = 4, gt = 9.

array[i] = 2 < v. array[lt] va array[i] örni almaşadi. lt++, i++.

[4, 2, 2, 5, 2, 6, 6, 6, 5, 7, 7, 8, 9]

11-sikl. i = 7, lt = 5, gt = 9.

array[i] = 6 == v. i++. Arrayda özgariş bölmaydi.

[4, 2, 2, 5, 2, 6, 6, 6, 5, 7, 7, 8, 9]

12-sikl. i = 8, lt = 5, gt = 9.

array[i] = 5 < v. array[lt] va array[i] örni almaşadi. lt++, i++.

[4, 2, 2, 5, 2, 5, 6, 6, 6, 7, 7, 8, 9]

12-sikl. i = 9, lt = 6, gt = 9.

array[i] = 7 > v. array[gt] va array[i] örni almaşadi. Aniqroği özgariş bölmaydi, çunki i = gt. gt--.

[4, 2, 2, 5, 2, 5, 6, 6, 6, 7, 7, 8, 9]

i = 9, gt = 8 bölib qolgani uçun, sikl töxtatiladi. Endi array'ning v çap çegarasidan (lt) çap qismi hamda öng çegarasidan (lt) öng qismi uçun tartiblaşni qaytadan boşlaymiz (rekursiya).

[4, 2, 2, 5, 2, 5, ...]

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

Işlaş prinsipini tuşuntira oldim deb umid qilaman.

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-3-way.js

Qöşimça optimallaştiriş

Yuqoridagi misolda e'tibor bergan bölsangiz, 6-siklda 7 sonining örni ikki marta almaşdi. aslida 7 sonini biz v dan katta bölgani uçun joyida qoldirsak bölardi. Muammo bu yerda batafsilroq tuşuntirilgan:

https://cs.stackexchange.com/questions/22389/quicksort-dijkstra-3-way-partitioning-why-the-extra-swapping

Daykstra'ning biz körib ötgan algoritmining işlaş tartibi şunday. Biz kodni sodda, tuşunarli qoldiriş hisobiga ortiqça almaştirişlarga köz yumganmiz. Ortiqça almaştirişlardan qoçiş mumkinmi? Mumkin, boşqaçaroq algoritm yoziş bilan.


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.