칵테일 정렬

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
칵테일 정렬

칵테일 셰이커 정렬(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일에 확인함.