Koktel sortiranje

Koktel sortiranje, još poznato kao dvosmerno bubble sortiranje, sortiranje mešanjem (shaker sort) (varijacija sortiranja izborom), je varijacija bubble sortiranja i sortiranja poređenjem. Algoritam se razlikuje od algoritma bubble sortiranja po tome što vrši sortiranje u oba pravca pri svakom prolasku kroz niz. Ovaj algoritam je samo malo teži za implementaciju od bubble sortiranja i rešava „problem kornjače“.

Pseudokod

Najjednostavniji oblik koktel sorta prolazi kroz niz svaki put:

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

Prvi prolazak sleva nadesno pomera najveći element na svoje mesto na kraju niza, a prolaz zdesna nalevo pomera najmanji element na svoje mesto na početku niza. Svaki naredni prolazak pomera sledeći najveći i sledeći najmanji na svoje mesto. Nakon i prolazaka kroz petlju, prvih i poslednjih i elemenata su na svojim mestima. Skraćivanjem dela niza koji je sortiran, broj operacija može biti prepolovljen.

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

Razlika u odnosu na bubble sortiranje

Koktel sortiranje je blago izmenjen bubble sort. Razlikuje se po tome što umesto da prolazi kroz niz sa početka na kraj, prolazi i sa kraja na početak. Zbog toga je malo brži od standardnog bubble sortiranja.

Primer niza koji pokazuje ovo tvrđenje je (2,3,4,5,1), koji se može sortirati kroz samo jedan prolazak ako se koristi koktel sort, a četiri prolaska ako se koristi bubble sort. U proseku je koktel sortiranje dva puta brže od bubble sortiranja.

Još jedna optimizacija algoritma je ta da se pamti poslednja zamena. U sledećoj iteraciji neće biti zamena ispod ove granice i algoritam ima manje prolazaka. Zbog toga što se sortiranje vrši u oba smera, broj prolazaka će se smanjivati što dovodi do smanjenja ukupnog vremena izvršavanja.

Složenost

Složenost koktel sortiranja u O notaciji je $O(n^{2})$ u najgorem i prosečnom slučaju, ali se približava $O(n)$ ako je niz skoro sortiran pre primene algoritma, na primer, ako je svaki element na poziciji koja se razlikuje najviše za k (k ≥ 1) mesta od pozicije na kojoj će završiti, složenost koktel sortiranja postaje $O(k*n)$.

Koktel sortiranje je ukratko opisano u knjizi The Art of Computer Programming, zajedno sa sličnim poboljšanjima bubble sortiranja. Da zaključimo, Knut je izjavio (Knuth (1998). стр. 110):

Nijedno od ovih poboljšanja ne vodi do algoritma boljeg od sortiranja umetanjem; a već znamo da sortiranje umetanjem nije pogodno za veliko  N. [...] Ukratko, deluje kao da je sve što nudi bubble sortiranje privlačno ime i činjenica da vodi zanimljivim teoretskim problemima.

— D. E. Knuth

Reference

• Paul E. Black and Bob Bockholt, "bidirectional bubble sort", in Dictionary of Algorithms and Data Structures (online), Paul E. Black, ed., U.S. National Institute of Standards and Technology. 24 August 2009. (accessed: 5 Feb 2010)
• R. Hartenstein: THE GRAND CHALLENGE TO REINVENT COMPUTING - A new World Model of Computing; Proc. CSBC_2010, July 20–23, 2010, Belo Horizonte, Brasil, [1]