Квиксорт

Квиксорт

Намена сортирање Структура података варира Временска компл. O(n logn) до O(n²) Меморијска компл. O(logn) до O(n) Стабилан не

Квиксорт (енгл. quicksort, qsort; од енгл. quick, брз, брзо; и енгл. sort, сортирање) је познат алгоритам сортирања који ради на принципу подели па владај, а развио га је Тони Хор 1960. године.

Принцип рада алгоритма

Следи опис рада алгоритма који елементе сортира у растућем поретку. Основни принцип рада алгоритма се дели у три следеће целине:

• Изабирање пивот-елемента на датом интервалу
• Распоред свих елемената мањих или једнаких овом пивот-елементу лево од њега, а свих већих десно од њега у низу
• Рекурзивно понављање овог поступка на новонастале интервале лево и десно од овог пивот-елемента

Опширнији опис

Алгоритам на почетку добије низ и леву и десну границу интервала кога треба сортирати. За ове границе мора да важи да лева има мањи индекс од десне, иначе се алгоритам прекида. Унутар тог интервала, алгоритам изабере тзв. пивот-елемент, који се обично узима са његове средине или њене околине. Потом, алгоритам замењује места пивот-елемента и последњег елемента у низу (из разлога који ће бити споменут касније) и сортирање може да почне. Алгоритам пролази кроз цео задат интервал и све елементе који су мањи или једнаки том пивот-елементу слаже на прво, друго, треће итд. место у низу. Притом елементи који су се затекли на том првом, другом, трећем итд. месту замењују (енгл. swap) своја места за места нађених елемената. Елементи који се већ налазе на неком од ових места и испуњавају услов да на њему остану се не премештају.

По завршетку овог процеса, пивот-елемент са краја интервала се ставља на крај овог низа, иза задњег постављеног елемента. Тај елемент је сад на свом месту и неће бити више потребе премештати га. Због овога је на почетку и био премештен на крај — да се током размештања не би морало пратити његово место у низу те да премештање на крај буде лакше. Дати интервал је сад овим пивот-елементом подељен на два подинтервала од којих леви садржи све елементе њему мање или једнаке, а десни све оне који су од њега већи. Алгоритам се сада понавља за ова два новонастала интервала.

Процес прераспоређивања и дељења се на даљим подинтервалима понавља док се не дође до интервала дужине један или нула, у којима је елемент већ на почетку алгоритма на свом месту.

Пример

Рецимо да квиксортом треба у растућем поретку сортирати следећи низ:

2 5 11 8 7 9 1 15 16 4

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

2 5 11 8 7 9 1 15 16 4
2 5 11 8 7 4 1 15 16 9

2 5 11 8 7 4 1 15 16 9
2 5 11 8 7 4 1 15 16 9
2 5 8 11 7 4 1 15 16 9
2 5 8 7 11 4 1 15 16 9
2 5 8 7 4 11 1 15 16 9
2 5 8 7 4 1 11 15 16 9

Овде је пролазак кроз низ завршен и пивот-елемент, број 9, ће заузети своје коначно место у низу. Овакви елементи ће надаље имати плаву боју.

2 5 8 7 4 1 9 15 16 11

Према опису алгоритма, поступак се сад понавља на левом новонасталом подинтервалу. Надаље ће неки кораци бити прескочени као небитни за праћење

2 5 8 7 4 1   15 16 11
2 5 8 1 4 7   15 16 11

2 5 1 8 4 7   15 16 11
2 5 1 4 8 7   15 16 11
2 5 1 4 7 8   15 16 11

И опет на левом новонасталом подинтервалу:

2 5 1 4   8   15 16 11
2 5 4 1   8   15 16 11

Како овај пут нема елемента мањег или једнаког пивот-елементу, пивот-елемент ће доћи на прво место у подинтервалу, што значи да ће дужина левог подинтервала бити нула. Алгоритам над овим делом се сместа завршава и како исти нема даљих подела, прелази се на десни део настао приликом последње поделе: део 2, 5, 4. Надаље ће и делови проласка кроз низ (означавање зеленом бојом) бити прескакани.

1 2 5 4   8   15 16 11
  2 5 4   8   15 16 11
  2 4 5   8   15 16 11

  2 4     8   15 16 11
  2 4     8   15 16 11

  2       8   15 16 11
  2       8   15 16 11

          8   15 16 11
          8   15 16 11

Подсећање: до сада је сортиран интервал који се налази лево од првог пивот-елемента, деветке, и овако сортиран се може сложити погледом на плаве елементе у горњим листама: 1, 2, 4, 5, 7, 8 и 9 иза њега. Алгоритам сад прелази на десну страну тог првог дељења тј. десно од броја девет. За пивот-елемент се опет узима број на средини интервала.

              15 16 11
              15 11 16
              15 11 16

Но како су оба броја мања од њега, и остаје на крају интервала, где је као пивот-елемент био премештен. Следећи пивот-елемент је број 11, који завршава на почетку интервала, јер нема елемената који су му једнаки или мањи од њега.

              15 11
              11 15

А преостали број 15 се већ налази на свом месту (интервал дужине један).

                 15

Ако се погледа навише, видеће се да је овај интервал сортиран као 11, 15, 16. Што се сад може спојити са левом страном. Овај низ је сортиран:

1 2 4 5 7 8 9 11 15 16