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.