칵테일 정렬

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
칵테일 정렬
칵테일 정렬 시각화
분류정렬 알고리즘
자료 구조배열
최악 시간복잡도
최선 시간복잡도
평균 시간복잡도
공간복잡도

칵테일 셰이커 정렬(cocktail shaker sort)[1]양방향 거품 정렬(bidirectional bubble sort)[2] 또는 셰이커 정렬(shaker sort) 등으로도 불리는 거품 정렬의 변형이다. 거품 정렬과는 달리 매 라운드마다 리스트의 순서를 바꾼다.

의사코드[편집]

procedure cocktailShakerSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 2 do:
      if A[ i ] > A[ i + 1 ] then // test whether the two elements are in the wrong order
        swap( A[ i ], A[ i + 1 ] ) // let the two elements change places
        swapped := true
      end if
    end for
    if not swapped then
      // we can exit the outer loop here if no swaps occurred.
      break do-while loop
    end if
    swapped := false
    for each i in length( A ) - 2 to 0 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped // if no elements have been swapped, then the list is sorted
end procedure

소스 코드[편집]

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
}

각주[편집]

  1. 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. 
  2. 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. 2010년 2월 5일에 확인함.