5. 칵테일 정렬

출처: http://bitly .kr/XRuljTi

칵테일 정렬(cocktail sort)

칵테일 정렬의 과정을 나타낸 그림.

셰이커 정렬(shaker sort)라고도 한다.

리플 정렬, 셔플 정렬이라고도 한다.

쉐이커 모습.

홀수 번째 돌 때는 앞부터, 짝수 번째는 뒤부터 훑는 정렬.

당연하겠지만 이 정렬은 마지막과 처음이 번갈아가며 정렬된다.

제일 처음에 하나, 제일 뒤에 하나, 다시 제일 앞에 하나, 또 제일 뒤에 하나를 정렬하면서

마치 정렬하는 과정이 앞뒤로 마구 흔드는게 칵테일을 마구 흔들어 섞는것과 비슷해보인다 하여

칵테일(혹은 이름을 합쳐서 칵테일 셰이커) 정렬이라는 이름이 붙었다.

 

버블 정렬의 극단적인 비교 횟수를 줄이기 위해 버블 정렬을 조금 변형한 알고리즘이다.

위에서 아래로 한 방향이 아니라, 아래에서 위로도 처리한다는 점에서 더 낮은 성능을 발휘.

그래서 거품 정렬 보다 2배 이상 빠르다.
하지만, 좋은 정렬이라고는 할 수 없음. 시간복잡도  

---

예제 c 코드

#include <stdio.h>
#include <stdlib.h>



void cocktail_sort(int *data, int n)
{
  int i, tmp, k, left, right = n-1, shift = -1;



  while((left=shift) < right)
  {
    for(i = left+1; i < right; i++)
    {
      if (data[i] > data[i+1])
      {
        tmp = data[(shift=i)];
        data[i] = data[i+1];
        data[i+1] = tmp;
       
        for(k = 0; k < n; k++)
          if (k == i || k == i+1) printf("[%2d] ", data[k]); else printf(" %2d  ", data[k]);
        printf("\n");
      }
      else { for(k = 0; k < n; k++) printf(" %2d  ", data[k]); printf("\n"); }
    }
    printf("\n");
      
    for(i = (right=shift)-1; i > left; i--)
    {
      if (data[i] > data[i+1])
      {
        tmp = data[(shift=i)];
        data[i] = data[i+1];
        data[i+1] = tmp;
       
        for(k = 0; k < n; k++)
          if (k == i || k == i+1) printf("[%2d] ", data[k]); else printf(" %2d  ", data[k]);
        printf("\n");
      }
      else { for(k = 0; k < n; k++) printf(" %2d  ", data[k]); printf("\n"); }
    }
    printf("\n");
  }
}



int main()
{
  int i, n = 6;
  int data[6] = { 40, 25, 13, 17, 75, 7 };
 
  printf("========== 정렬 전 ==========\n");
  for(i = 0; i < n; i++) printf(" %2d  ", data[i]); printf("\n");



  printf("\n========== 정렬 ==========\n");
  cocktail_sort(data, n);



  printf("========== 정렬 후 ==========\n");
  for(i = 0; i < n; i++) printf(" %2d  ", data[i]); printf("\n");

  system("pause");
  return 0;
}

위의 링크에 들어가면. 코드 실행 결과를 볼 수 있다.

하지만 코드 실행 결과는 이 글에서도 볼 수 있다.

---

========== 정렬 전 ==========
 40   25   13   17   75    7  

========== 정렬 ==========
[25] [40]  13   17   75    7  
 25  [13] [40]  17   75    7  
 25   13  [17] [40]  75    7  
 25   13   17   40   75    7  
 25   13   17   40  [ 7] [75] 

 25   13   17  [ 7] [40]  75  
 25   13  [ 7] [17]  40   75  
 25  [ 7] [13]  17   40   75  
[ 7] [25]  13   17   40   75  

  7  [13] [25]  17   40   75  
  7   13  [17] [25]  40   75  
  7   13   17   25   40   75  

  7   13   17   25   40   75  

========== 정렬 후 ==========
  7   13   17   25   40   75  

---

칵테일 정렬의 성능은 최상의 경우 O(n) , 최악의 경우