칵테일 정렬

칵테일 정렬
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도
최선 시간복잡도
평균 시간복잡도
공간복잡도

칵테일 셰이커 정렬(영어: cocktail shaker sort 칵테일 셰이커 소트^[*])^[1], 양방향 거품 정렬(영어: bidirectional bubble sort 비디렉셔널 버블 소트^[*])^[2] 또는 셰이커 정렬(영어: shaker sort 셰이커 소트^[*])은 정렬 알고리즘 중 하나로, 버블 정렬의 변형이다.

알고리즘

버블 정렬과 다른 점은 버블 정렬은 배열을 앞부터 뒤까지 반복하며 두 수를 바꾸지만, 칵테일 정렬은 배열을 앞에서 뒤까지, 다음은 뒤에서 앞까지, 다음은 다시 앞에서 뒤까지 반복하는 식으로 순서만 다르다.

소스 코드

C++

template 〈typename BidirectionalIterator〉
void cocktailShaker(BidirectionalIterator first, BidirectionalIterator last)
{
    BidirectionalIterator shift = first;
    BidirectionalIterator i;

    while (first < last) {
        i = first;
        while (++i < last) {        // [shift, last)
            if (*i < *(i-1)) {
                std::iter_swap(i, i-1);
                shift = i;
            }
        }
        last = shift;

        i = last;
        while (--i > first) {        // (shift, first]
            if (*i < *(i-1)) {
                std::iter_swap(i, i-1);
                shift = i;
            }
        }
        first = shift;
    }
}

스칼라

def cocktailShaker(arr: Array[Int]):Array[Int] =  {

  var i = 0
  var tmp = 0
  var lastIdx = arr.length - 1
  var swapped  = true

  do {
      println("i:"+i)

      if (swapped) {
        for (j <- i to lastIdx-i-1) {
          if (arr(j) > arr(j+1)) {
            tmp = arr(j+1)
            arr(j+1) = arr(j)
            arr(j) = tmp
            swapped = true
          }
        }
        arr.map(x=> print(x+" "))
        println
      }

      if (swapped) {
       swapped = false

        for (j <- lastIdx-i-1 to i by -1) {
          if (arr(j) > arr(j+1)) {
            tmp = arr(j+1)
            arr(j+1) = arr(j)
            arr(j) = tmp
            swapped = true
          }
        }

        arr.map(x=> print(x+" "))
        println
      }

      i = i + 1

  } while (swapped)

  arr
}

파이썬

def cocktailShaker(arr):
    
    lastIdx = len(arr) - 1
    swapped  = True
    i = 0

    while swapped: 
        swapped = False
        for j in range(i, lastIdx-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True

        if swapped:
            for j in reversed(range(i, lastIdx-i)):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    swapped = True
        
        i = i + 1
    return arr

각주

↑ Knuth, Donald E. (1973). 〈Sorting by Exchanging〉. 《Art of Computer Programming》. 3. Sorting and Searching 1판. Addison-Wesley. 110–111쪽. ISBN 0-201-03803-X.
↑ Black, Paul E.; Bockholt, Bob (2009년 8월 24일). 〈bidirectional bubble sort〉. Black, Paul E. 《Dictionary of Algorithms and Data Structures》. National Institute of Standards and Technology. 2013년 3월 16일에 원본 문서에서 보존된 문서. 2010년 2월 5일에 확인함.