Dijkstra'ning 3-way partitioning quicksort algoritmi bilan tanishib chiqqan bo'lsangiz kerak. U quicksort'dagi bir xil key'lar uchragan holatida ishlash vaqti ortishining oldini oladi. Biz 3-way quicksort'ga qaytamiz, bu safar bo'luvchi element - pivot'ni key belgilaridan olamiz.

3-way Radix Quicksort ishlash tartibi

Bizda quyidagi ro'yhat bor bo'lsin:

she
sells
seashells
by
the
sea
shore
the
shells
she
sells
are
surely
seashells

Birinchi key - "she" ning birinchi belgisi - s ni bo'luvchi element deb olamiz va ro'yhatni s dan kichik hamda s dan katta ko'rinishida tartiblaymiz:

by
are
---
seashells
she
seashells
sea
shore
surely
shells
she
sells
sells
---
the
the

3 qismga ajratdik. pivot oraliq "s..." ning chap qismi uchun yana 3 qismga ajratishni qo'llaymiz.

are
by
---
seashells
she
seashells
sea
shore
surely
shells
she
sells
sells
---
the
the

Pivot oraliq uchun esa bo'lishga birinchi key'dagi s dan keyingi belgini tanlaymiz. Birinchi so'z - "seashells", s dan keyingi harf - e. Demak, e bo'luvchi bo'lib, "s..." key'lar "se" dan kichkina, "se" bilan boshlanuvchi va "se" dan katta qilib 3 ga bo'linadi.

are
---
by
---
seashells
sells
seashells
sea
sells
---
shells
she
surely
shore
she
---
the
the

"s" bilan boshlanuvchi key'lar ichida "se" dan kichkinalari bo'lmagani uchun "se" bilan boshlanuvchi va "se" dan katta qismlarga ajraldi. Ularni ham alohida-alohida partition'ga ajratamiz

are
---
by
---
seashells
seashells
sea
---
sells
sells
---
shells
she
shore
she
---
surely
---
the
the

Shu tariqa, partition'ga ajratishni davom ettiramiz:

are
---
by
---
sea
seashells
seashells
---
sells
sells
---
shells
she
she
---
shore
---
surely
---
the
the

Keyingi qadam:

are
---
by
---
sea
---
seashells
seashells
---
sells
sells
---
she
she
---
shells
---
shore
---
surely
---
the
the

Yakunda tartiblangan ro'yhat quyidagi ko'rinishga keladi:

are
by
sea
seashells
seashells
sells
sells
she
she
shells
shore
surely
the
the

Kod

Kod ham 3-way partitioning funksiyasining biroz o'zgargan varianti.