3-way Radix Quicksort
Dijkstra'ning 3-way partitioning quicksort algoritmi bilan tanişib çiqqan bölsangiz kerak. U quicksort'dagi bir xil key'lar uçragan holatida işlaş vaqti ortişining oldini oladi. Biz 3-way quicksort'ga qaytamiz, bu safar böluvçi element - pivot'ni key belgilaridan olamiz.
3-way Radix Quicksort işlaş tartibi
Bizda quyidagi röyhat bor bölsin:
she
sells
seashells
by
the
sea
shore
the
shells
she
sells
are
surely
seashells
Birinçi key - "şe" ning birinçi belgisi - s ni böluvçi element deb olamiz va röyhatni s dan kiçik hamda s dan katta körinişida tartiblaymiz:
by
are
seashells
she
seashells
sea
shore
surely
shells
she
sells
sells
the
the
3 qismga ajratdik. pivot oraliq "s..." ning çap qismi uçun yana 3 qismga ajratişni qöllaymiz.
are
by
seashells
she
seashells
sea
shore
surely
shells
she
sells
sells
the
the
Pivot oraliq uçun esa bölişga birinçi key'dagi s dan keyingi belgini tanlaymiz. Birinçi söz - "seashells", s dan keyingi harf - e. Demak, e böluvçi bölib, "s..." key'lar "se" dan kiçkina, "se" bilan boşlanuvçi va "se" dan katta qilib 3 ga bölinadi.
are
by
seashells
sells
seashells
sea
sells
shells
she
surely
shore
she
the
the
"s" bilan boşlanuvçi key'lar içida "se" dan kiçkinalari bölmagani uçun "se" bilan boşlanuvçi 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
Şu tariqa, partition'ga ajratişni davom ettiramiz:
are
by
sea
seashells
seashells
sells
sells
şells
şe
şe
şore
surely
the
the
Keyingi qadam:
are
by
sea
seashells
seashells
sells
sells
şe
şe
şells
şore
surely
the
the
Yakunda tartiblangan röyhat quyidagi körinişga keladi:
are
by
sea
seashells
seashells
sells
sells
şe
şe
shells
şore
surely
the
the
Kod
Kod ham 3-way partitioning funksiyasining biroz özgargan varianti.