Сортирање поделом

Сортирање (разврставање) поделом (енгл. Unshuffle sort) је алгоритам сортирања.

Увод

UnShuffle sort је сортирање поделом или сортирање обједињавањем које је развијено од стране Арт С. Кагела. UnShuffle је најефикаснији када се сортирају подаци који имају малу ентропију, у смислу да се подаци добро уређени или садрже добро уређене под-секвенце. Тренутна имплементација је резултат вишегодишњег експериментирања. Сортирање укључује двије фазе. Током прве фаза поделе предмети се распоређују у промјењивом броју уређених листи коришћењем структуре која смањује број поређења. Након што су сви предмети распоређени, сортиране листе се обједињују у једну иyлаyну листу. УнСхуффле је један од ретких сортова које се могу директно применити на повезане листе.

Алгоритам користи структуру података под називом 'стуб' (енгл. pile) која је уређени ред у коме дозвољено убацивање елемената на почетку листе, уколико је нови елемент мањи или једнак тренутној глави или на крају листе, ако је нови елемент већа или једнак репу листе. Није дозвољено уметање елемената између постојећих елемената. То се обично спроводи коришћењем двоструко повезане листе листи са покаyивачима на почетак и крај двоструко повезане листе садржи елементе стуба као и следећи и претходни стуб. Детаљи уклањања елемната из улазне листе и додавањем елемената у излазну листу су изостављени као посебне имплементације.

Најбољи случај за УнСхуффле у случају потпуно уређених или обрнуто урђених низова података са само једним стубом кориштењем н-1 поређења (с препорученом оптимизацију) и без обједињавања. Нема најгорег случаја и може се показати да нема низа чија је сложеност ваћа од О ((К / 4) * Н) за фазу I + О (Н * (лог К)) за фазу II помоћу коришћењем идеалног обједињавања yа фазу II, гдје је К број стубова креираним током фазе распоређивања (фаза I).

Будући да сортира повезане листе, а не низове података само се покаyивачи премештају и због структуре стуба не постоје скупе замене, тако да време сортирања зависи од величине податка и сложености кључа.

Фаза I - Фаза поделе

1. Узми први елемент и креирај стуб #1 са елементом#1 као главу и реп.
2. Ако нема више елемента пређи на фазу II.
3. Узми следећи елемент.
4. Одаберите посљедњи стуб за поређење.
5. Упореди са врхом стуба.
6. Ако једнак стви на врх стуба, пређи на корак 2.
7. Ако је мањи, а то није први стуб означи претходни стуб и пређи на корак 5.
8. Ако је мање и то јесте први стуб, стави елемент на врх стуба и пређи на корак 2.
9. Ако је већи, а то није посљедњи стуб стави на врх следећег стуба (који је претходни упоређен), пређи на корак 2, у супротном елемент је већи од краја стуба.
10. Упореди са крајем тренутног стуба.
11. Ако једнак стави на крај стуба, пређи на корак 2.
12. Ако је већи, а то није први стуб оyначи претходни стуб, пређи на корак 10.
13. Ако је мањи и то је посљедњи стуб креирај нови стуб од елемента и додати у листу стубова, пређи на корак 2.
14. Убаци на крај следећег стуба, пређи на корак 2.

Фаза II – Фаза обједињавања

Користи иделано обједињавање за спајање стубова креираних у фази I. Иделно обједињавање је алгоритам који се покаyује као најбољи за обједињавање уређених редова.

Алгоритам идеалног обједињавања

1. Уреди главе улазних редова у низ или повезану листу.
2. Сортирај листу улазних редова у односу на релативну вредност елементната са врха сваког реда(како је листа редова типично мала скоро сваки сорт се може употребити за ово).
3. Испиши елемент са врха првог реда.
4. Ако је први ред празан онда га одбаци. Ако нема више редова изађи, у супротном други ред сада постаје први предји на, корак 3, у супротном пређи на корак 5.
5. Ако је први ред једини преостао, пређи на корак 3.
6. Упореди нови врх првог реда са новим врхом другог реда. Ако је мањи пређи на корак 3.
7. Бинарном претрагом пронађи други, пронађи где тернутни врх провг реда припад у листи редова I убаци први ред на том месту у листи. Други ред је сада први, пређи на корак 3.

Оптимизације

Оптимизација Фазе I

Прати да ли је последњи елемент постављен на почетку или на крају неког стуба и почни поређење за следећи елемент на истој страни (на пример уколико је последњи елемент постављен на крају стуба почни поређење са последњим елементом из последњег стуба а не са почетним и пређи на поређење са поченим уколико је елемент већи од последњег у последњем стубу). У општем случају и за јако уређене податке ово је једина оптимизација оснпвног алгоритма, у порсеку, Н/2 поређења I највише Н-1 поређења за обрнуто уређене улазе.

Оптимизација Фазе II

Општи алгоритам Идеалног Обједињавања може се понољшати бољим упозанвањем Фазе Поделе:

Када се користи за обејдињавање Унсхуффле сорта, креирање листе редова и почетно сортирање стубова није потребно с обзиром да подела креира стубове уређене по њиховим почетним елемнетима. У овом случају обједињавање почиње у кораку #3.

С обзиром да поролаз кроз елемнте може бити припремљен за сваки стуб пре него што је било који други стуб припремљен или придодат је предност за поређење следећег елмента из првог стуба са почетним из другог стуба, након исписивања почетног елемента из стуба, да би се одредило да ли је потербно преуређеивање претраге, а ако није онда елмент може одмах да се испише и поступак се понавља.

Оптимеизација за специјалне улазе

Низови могу бити третирани и као „ток“ и подвргнути итеративном сортирању, а не креирању повезане листе од низа. Због позива функције у најбољем случају предност овога може бити маргинална, али коришћење не-итеративне врезије која низ третира као ток може бити и боља.

Унсхуффле није стабилан алгоритам сортирања али стабилност се може постићи убацивањем улазног записа на крај кључа сортирања.

Елиминација дуплираног запис се може извести и током Фазе I и током Фазе II или одложити до Фазе II.

Литература

• UnShuffle Sort on nist.gov
• UnShuffle. Not Quite a Sort, Computer Language Magazine, Nov. 1986