WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

3-way Radix Quicksort

Sorting

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.