칵테일 정렬

칵테일 셰이커 정렬(), 양방향 거품 정렬() 또는 셰이커 정렬()은 정렬 알고리즘 중 하나로, 버블 정렬의 변형이다.

알고리즘 

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

소스 코드

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
}

각주 

정렬 알고리즘
안정 정렬
비교 정렬