Коктел сортирање

С Википедије, слободне енциклопедије

Коктел сортирање, још познато као двосмерно буббле сортирање, сортирање мешањем (схакер сорт) (варијација сортирања избором), је варијација буббле сортирања и сортирања поређењем. Алгоритам се разликује од алгоритма буббле сортирања по томе што врши сортирање у оба правца при сваком проласку кроз низ. Овај алгоритам је само мало тежи за имплементацију од буббле сортирања и решава „проблем корњаче“.

Псеудокод[уреди | уреди извор]

Најједноставнији облик коктел сорта пролази кроз низ сваки пут:

procedure koktelSort( A : niz koji treba sortirati ) defined as:
  do
    zamenjeno := false
    for each i in 0 to length( A ) - 2 do:
      if A[ i ] > A[ i + 1 ] then // poredi 2 uzastopna elementa
        zameni( A[ i ], A[ i + 1 ] ) // menja 2 elementa
        zamenjeno := true
      end if
    end for
    if zamenjeno = false then
      // izlazak iz petlje ako nije bilo zamena
      break do-while loop
    end if
    zamenjeno := false
    for each i in length( A ) - 2 to 0 do:
      if A[ i ] > A[ i + 1 ] then
        zameni( A[ i ], A[ i + 1 ] )
        zamenjeno := true
      end if
    end for
  while zamenjeno // ako nikoja 2 elementa nisu zamenjena, niz je sortiran
end procedure

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

procedure koktelSort( A : niz koji treba sortirati ) defined as:
  // `pocetak` i `kraj` označavaju indeks prvog i poslednjeg elementa
  pocetak := -1
  kraj := length( A ) - 2
  do
    zamenjeno := false
    // inkrementiramo `pocetak` jer su elementi pre njega sortirani
    pocetak := pocetak + 1
    for each i in pocetak to kraj do:
      if A[ i ] > A[ i + 1 ] then
        zameni( A[ i ], A[ i + 1 ] )
        zamenjeno := true
      end if
    end for
    if zamenjeno = false then
      break do-while loop
    end if
    zamenjeno := false
    // dekrementiramo `kraj` jer su elementi posle njega sortirani 
    kraj := kraj - 1
    for each i in kraj to pocetak do:
      if A[ i ] > A[ i + 1 ] then
        zameni( A[ i ], A[ i + 1 ] )
        zamenjeno := true
      end if
    end for
  while zamenjeno
end procedure

Разлика у односу на буббле сортирање[уреди | уреди извор]

Коктел сортирање је благо измењен буббле сорт. Разликује се по томе што уместо да пролази кроз низ са почетка на крај, пролази и са краја на почетак. Због тога је мало бржи од стандардног буббле сортирања.

Пример низа који показује ово тврђење је (2,3,4,5,1), који се може сортирати кроз само један пролазак ако се користи коктел сорт, а четири проласка ако се користи буббле сорт. У просеку је коктел сортирање два пута брже од буббле сортирања.

Још једна оптимизација алгоритма је та да се памти последња замена. У следећој итерацији неће бити замена испод ове границе и алгоритам има мање пролазака. Због тога што се сортирање врши у оба смера, број пролазака ће се смањивати што доводи до смањења укупног времена извршавања.

Сложеност[уреди | уреди извор]

Сложеност коктел сортирања у О нотацији је у најгорем и просечном случају, али се приближава ако је низ скоро сортиран пре примене алгоритма, на пример, ако је сваки елемент на позицији која се разликује највише за к (к ≥ 1) места од позиције на којој ће завршити, сложеност коктел сортирања постаје .

Коктел сортирање је укратко описано у књизи Тхе Арт оф Цомпутер Программинг, заједно са сличним побољшањима буббле сортирања. Да закључимо, Кнут је изјавио (Кнутх (1998). стр. 110):

Ниједно од ових побољшања не води до алгоритма бољег од сортирања уметањем; а већ знамо да сортирање уметањем није погодно за велико  Н. [...] Укратко, делује као да је све што нуди буббле сортирање привлачно име и чињеница да води занимљивим теоретским проблемима.

— D. Е. Кнутх[1]


Референце[уреди | уреди извор]

  • Паул Е. Блацк анд Боб Боцкхолт, "бидирецтионал буббле сорт", ин Дицтионарy оф Алгоритхмс анд Дата Струцтурес (онлине), Паул Е. Блацк, ед., У.С. Натионал Институте оф Стандардс анд Тецхнологy. 24 Аугуст 2009. (аццессед: 5 Феб 2010)
  • Р. Хартенстеин: ТХЕ ГРАНД ЦХАЛЛЕНГЕ ТО РЕИНВЕНТ ЦОМПУТИНГ - А неw Wорлд Модел оф Цомпутинг; Проц. ЦСБЦ_2010, Јулy 20–23, 2010, Бело Хоризонте, Брасил, [1]
  1. ^ Тхе Арт оф Цомпутер Программинг, Вол. 3: Сортинг анд Сеарцхинг, Сецонд Едитион, Аддисон-Wеслеy, 1998.