TIL. 123 칵테일 정렬

셰이커 정렬(shaker sort)라고도 한다.
리플 정렬, 셔플 정렬이라고도 한다.

홀수 번째 돌 때는 앞부터, 짝수 번째는 뒤부터 훑는 정렬.
당연하겠지만 이 정렬은 마지막과 처음이 번갈아가며 정렬된다.
제일 처음에 하나, 제일 뒤에 하나, 다시 제일 앞에 하나, 또 제일 뒤에 하나를 정렬하면서
마치 정렬하는 과정이 앞뒤로 마구 흔드는게 칵테일을 마구 흔들어 섞는것과 비슷해보인다 하여
칵테일(혹은 이름을 합쳐서 칵테일 셰이커) 정렬이라는 이름이 붙었다.

버블 정렬의 극단적인 비교 횟수를 줄이기 위해 버블 정렬을 조금 변형한 알고리즘이다.
위에서 아래로 한 방향이 아니라, 아래에서 위로도 처리한다는 점에서 더 낮은 성능을 발휘.
그래서 거품 정렬 보다 2배 이상 빠르다.하지만, 좋은 정렬이라고는 할 수 없음. 시간복잡도  

#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;
}
출처: https://blog.tomclansys.com/52?category=1066976 [톰 클란시의 IT 블로그:티스토리]