Брзо сортирање са више кључева (енгл. Multi-key quicksort),Овај чланак укључује јавно власништво преузето из дела Paul E. Black. multikey Quicksort Dictionary of Algorithms and Data Structures. NIST. који се још назива и тросмерно радикс брзо сортирање (енгл. 3-Way Radix Quicksort) јесте алгоритам за сортирање стрингова. Овај алгоритам је заснован на идеји коју је првобитно предложио П. Шеклтон, а касније су га унапредили Џон Бентли и Роберт Сеџвик 1990. годинa. Bentley, Jon; Sedgewick, Robert (1997). . . Proc. Annual ACM-SIAM Symp. on Discrete Algorithms (SODA). . Настао је као комбинација брзог сортирања (енгл. Quicksort), и радикс сортирања (енгл. Radix sort), прилагођена за ефикасно сортирање стрингова са заједничким префиксима.
Опис За разлику од класичног брзог сортирања, који стрингове пореди као целину, овај алгоритам посматра само један карактер у тренутку на позицији д. Низ стрингова се дели на три групе у односу на карактер пивот елемента и то по следећем:
стрингови чији је карактер на позицији д мањи од карактера пивота стрингови са истим карактером на тој позицији стрингови чији је карактер на позицији д већи од карактера пивота
Средња група са истим карактером на тој позицији се даље рекурзивно сортира почев од следећег карактера, док се преостале две групе такође рекурзивно сортирају и даље по истом карактеру. Поступак рада алгоритма приказан је следећим псеудокодом:algorithm sort(a: array of string, d : integer) is if length(a) ≤ 1 or d ≥ K then return
p:= pivot(a,d) i, j:= partition(a, d, p)
sort(a[0:i], d) sort(a[i:j], d+1) sort(a[j:lenght(a)), d])
Пример Рецимо да треба да сортирамо следећи низ речи: шав шал шума шала шапа.шав шал шума шала шапа
Први корак - партиционисање по 1. карактеру (d=0) Пивот елемент је прва реч шав, а посматра се њен карактер на позицији 0, слово "ш". Пошто свих 5 речи почињу словом "ш", ниједна реч не иде у леву (мању) или десну (већу) групу већ све одлазе у средњу групу једнаку пивоту. Низ остаје неизмењен, али се цела група помера за 1 карактер.
Други корак - партиционисање по 2. карактеру (д=1) Пивот је опет прва реч, шав, а посматра се карактер на позицији 1 "а". Пролазимо кроз друге речи и упоређујемо њихов други карактер са а. +реч2. карактероднос према "а"шаваједнакошалаједнакошумаувећешалааједнакошапааједнако Видимо да шума једина одступа јер карактер "у" долази после слова "а" у азбуци и иде у десну групу:шав шал шала шапа | шумаНакон партиционисања речи су распоређење у следеће групе:
средња група: шав, шал, шала, шапа
десна група: шума и већ је сортирана
Трећи корак - партиционисање шав, шал, шала, шапа по 3. карактеру (д=2) Пивот елемент је шав, a посматра се карактер на позицији 2 "в". +реч3. карактероднос према "в"шаввједнакошаллвећешалалвећешапапвеће Реч шав остаје једина у својој групи јер нема мањих ни једнаких, а а остале три иду у десну групу:шав | шал шала шапаНакон партиционисања речи су распоређење у следеће групе:
лева/средња група: шав и сортирана је десна група: шал, шала, шапа и врши се рекурзивно сортирање даље на позицији д=2
Четврти корак - партиционисање шал, шала, шапа по 3. карактеру (д=2) Пивот елемент је шал, а посматра се карактер на позицији 2 "л". +реч3. карактероднос према "л"шаллједнакошалалједнакошапапвеће Након партиционисања речи су распоређење у следеће групе:
средња група: шал, шала и врши се рекурзивно сортирање даље на позицији д=3 десна група: шапа и сортирана је шал шала | шапа
Пети корак - партиционисање шал, шала по 4. карактеру (д=3) Пивот елемент је шал а пошто реч шал има само 3 карактера, на позицији 3 нема више карактера и узима се вредност -1 (крај стринга). Реч шала на позицији 3 има карактер а, а свака стварна вредност карактера је већа од -1 тако да шала иде у десну групу. шал | шалаПошто је вредност пивота -1, средња група се даље рекурзивно не сортира јер услов в ≥ 0 није испуњен. Шал остаје сам сортиран.
Коначан резултат шав шал шала шапа шума
Перформансе Временска сложеност зависи од броја стрингова N, просечне дужине стринга W и расподеле карактера у улазном низу. У најгорем случају временска сложеност износи O(W · N log R), где је R број могућих карактера азбуке. У просечном случају сложеност може да достигне O(N log N) поређења, као и код класичног брзог сортирања, али се у пракси показује као веома ефикасан за сортирање већег број стрингова са заједничким префиксима.
Пошто алгоритам упоређује само један карактер у сваком кораку, избегава непотребно поређење целих стрингова, што га чини бржим од класичног квиксорта.
Додатни меморијски простор који алгоритам користи углавном потиче од рекурзивних позива и износи O(log N + W). Алгоритам није стабилан, јер редослед једнаких елемената није загарантован и током партиционисања долази до замене места елемената и не морају остати у истом међусобном редоследу као у почетном низу.
Види још
Брзо сортирање Радикс сортирање
Референце