Квиксорт — разлика између измена
Садржај обрисан Садржај додат
следе опис и пример. перформансе, историју и стабилност ћу препустити неком другом |
Нема описа измене |
||
Ред 2:
[[Слика:Sorting quicksort anim.gif|мини|280п|Анимација сорирања низа елемената квиксортом]]
'''Квиксорт''' (од {{јез-ен|quick}}, брз, брзо; {{јез-ен|sort}} сортирање) је познат [[алгоритам]] [[сортирање|сортирања]] који ради на принципу [[подели па владај (информатика)|подели па владај]], а развио га је [[Тони Хор]] [[1960]]. године.
== Принцип рада алгоритма ==
Следи опис рада алгоритма који елементе сортира у [[растући поредак|растућем поретку]]. Основни принцип рада алгоритма се дели у три следеће целине:
* Изабирање пивот-елемента на датом интервалу
* Распоред свих елемената мањих или једнаких овом пивот-елементу лево од њега, а свих већих десно од њега у низу
* [[Рекурзија|Рекурзивно]] понављање овог поступка на новонастале интервале лево и десно од овог пивот-елемента
=== Опширнији опис ===
Алгоритам на почетку добије низ и леву и десну границу интервала кога треба сортирати. За ове границе мора да важи да лева има мањи индекс од десне, иначе се алгоритам прекида. Унутар тог интервала, алгоритам изабере тзв. пивот-елемент, који се обично узима са његове средине или њене околине. Потом, алгоритам замењује места пивот-елемента и последњег елемента у низу (из разлога који ће бити споменут касније) и сортирање може да почне. Алгоритам пролази кроз цео задат интервал и све елементе који су мањи или једнаки том пивот-елементу слаже на прво, друго, треће итд. место у низу. Притом елементи који су се затекли на том првом, другом, трећем итд. месту замењују ({{јез-ен|swap}}) своја места за места нађених елемената. Елементи који се већ налазе на неком од ових места и испуњавају услов да на њему остану се не премештају.
По завршетку овог процеса, пивот-елемент са краја интервала се ставља на крај овог низа, иза задњег постављеног елемента. Тај елемент је сад на свом месту и неће бити више потребе премештати га. Дати интервал је сад овим пивот-елементом подељен на два подинтервала од којих леви садржи све елементе њему мање или једнаке, а десни све оне који су од њега већи. Алгоритам се сада понавља за ова два новонастала интервала.
Процес прераспоређивања и дељења се на даљим подинтервалима понавља док се не дође до интервала дужине један или нула, у којима је елемент већ на почетку алгоритма на свом месту.
== Пример ==
Рецимо да квиксортом треба у растућем поретку сортирати следећи низ:
2 5 11 8 7 9 1 15 16 4
Прво се изабире пивот-елемент отприлике на половини низа. У овом случају ће то бити број 9. Следи премештане свих елемената мањих или једнаких 9 на леву страну низа. Црвеном бојом виће означен пивот-елемент, а зеленом последњи елеменат низа на кога се преслажу елементи мањи или једнаки пивот-елементу.
2 5 11 8 7 '''<font color="#ff0000">9</font>''' 1 15 16 4
2 5 11 8 7 4 1 15 16 '''<font color="#ff0000">9</font>'''
'''<font color="#00bb00">2</font>''' 5 11 8 7 4 1 15 16 '''<font color="#ff0000">9</font>'''
2 '''<font color="#00bb00">5</font>''' 11 8 7 4 1 15 16 '''<font color="#ff0000">9</font>'''
2 5 '''<font color="#00bb00">8</font>''' 11 7 4 1 15 16 '''<font color="#ff0000">9</font>'''
2 5 8 '''<font color="#00bb00">7</font>''' 11 4 1 15 16 '''<font color="#ff0000">9</font>'''
2 5 8 7 '''<font color="#00bb00">4</font>''' 11 1 15 16 '''<font color="#ff0000">9</font>'''
2 5 8 7 4 '''<font color="#00bb00">1</font>''' 11 15 16 '''<font color="#ff0000">9</font>'''
Овде је пролазак кроз низ завршен и пивот-елемент, број 9, ће заузети своје коначно место у низу. Овакви елементи ће надаље имати плаву боју.
2 5 8 7 4 1 '''<font color="#0000ff">9</font>''' 15 16 11
Према опису алгоритма, поступак се сад понавља на левом новонасталом подинтервалу. Надаље ће неки кораци бити прескочени као небитни за праћење
2 5 8 '''<font color="#ff0000">7</font>''' 4 1 15 16 11
2 5 8 1 4 '''<font color="#ff0000">7</font>''' 15 16 11
2 5 '''<font color="#00bb00">1</font>''' 8 4 '''<font color="#ff0000">7</font>''' 15 16 11
2 5 1 '''<font color="#00bb00">4</font>''' 8 '''<font color="#ff0000">7</font>''' 15 16 11
2 5 1 4 '''<font color="#0000ff">7</font>''' 8 15 16 11
И опет на левом новонасталом подинтервалу:
2 5 '''<font color="#ff0000">1</font>''' 4 8 15 16 11
2 5 4 '''<font color="#ff0000">1</font>''' 8 15 16 11
Како овај пут нема елемента мањег или једнаког пивот-елементу, пивот-елемент ће доћи на прво место у подинтервалу, што значи да ће дужина левог подинтервала бити нула. Алгоритам над овим делом се сместа завршава и како исти нема даљих подела, прелази се на десни део настао приликом последње поделе: део 2, 5, 4. Надаље ће и делови проласка кроз низ (означавање зеленом бојом) бити прескакани.
'''<font color="#0000ff">1</font>''' 2 5 4 8 15 16 11
2 '''<font color="#ff0000">5</font>''' 4 8 15 16 11
2 4 '''<font color="#0000ff">5</font>''' 8 15 16 11
2 '''<font color="#ff0000">4</font>''' 8 15 16 11
2 '''<font color="#0000ff">4</font>''' 8 15 16 11
'''<font color="#ff0000">2</font>''' 8 15 16 11
'''<font color="#0000ff">2</font>''' 8 15 16 11
'''<font color="#ff0000">8</font>''' 15 16 11
'''<font color="#0000ff">8</font>''' 15 16 11
Подсећање: до сада је сортиран интервал који се налази лево од првог пивот-елемента, деветке, и овако сортиран се може сложити погледом на плаве елементе у горњим листама: 1, 2, 4, 5, 7, 8 и 9 иза њега. Алгоритам сад прелази на десну страну тог првог дељења тј. десно од броја девет. За пивот-елемент се опет узима број на средини интервала.
15 '''<font color="#ff0000">16</font>''' 11
15 11 '''<font color="#ff0000">16</font>'''
15 11 '''<font color="#0000ff">16</font>'''
Но како су оба броја мања од њега, ту и остаје. Следећи пивот-елемент је број 11.
15 '''<font color="#ff0000">11</font>'''
'''<font color="#0000ff">11</font>''' 15
А преостали број 15 се већ налази на свом месту (интервал дужине један).
'''<font color="#0000ff">15</font>'''
Ако се погледа навише, видеће се да је овај интервал сортиран као 11, 15, 16. Што се сад може спојити са левом страном. Овај низ је сортиран:
1 2 4 5 7 8 9 11 15 16
[[Категорија:Алгоритми сортирања]]
| |||