[c++] 알고리즘 - 칵테일 쉐이커 정렬

칵테일 쉐이커 정렬 (Cocktail Shaker Sort)

- Donald Knuth가 처음 제안

- 버블 정렬을 수정하여 매번 반복할 때마다 방향을 바꿔가며 원소의 위치를 결정하는 기법.

- 한 번은 가장 큰 원소가 결정되고, 그 다음에는 가장 작은 원소가 결정되고, 또 그 다음에는 2번째로 큰 원소가 결정되고...

 

 

 

 

소스 코드

1.
#include <iostream>
#include <time.h>

using namespace std;
const int N = 10000;

const int TRUE = 1;
const int FALSE = 0;

inline void swap(int a[], int i, int j)
{
  int t = a[i]; a[i] = a[j]; a[j] = t;
}

void printList(int a[])
{
 int i;
 for (i = 1; i < N; i++)
   cout << a[i] << ", ";

 cout << a[i] << endl;
}

void CheckSort(int a[], int n)
{
  int i, Sorted;
  Sorted = TRUE;
  for (i = 1; i < n; i++) {
    if (a[i] > a[i+1]) Sorted = FALSE;
    if (!Sorted) break;
  }
  if (Sorted) cout << "정렬 완료." << endl;
  else cout << "정렬 오류 발생." << endl;
}

int main()
{
 int array[N+1] = {-1,3,2,7,1,5};

 int i, j, k, l=N, m=1;
 int t=N;

 double start_time;

 

 for (i = 1; i <= N; i++) array[i] = rand(); //랜덤 배열원소

 start_time = clock();

 for(k = (N/2)+1 ; k >= 1 ; k--)
 {
  for(i=m;i<N;i++)
  {
   if(array[i]>array[i+1])
    swap(array,i,i+1);
   
  }
  l--; //끝에것은 빼고 정렬

  for(j=l; j>1; j--)
  {
   if(array[j]<array[j-1])
    swap(array,j,j-1);

  }
  m++; //앞에것은 빼고 정렬
 } 
 cout << "칵테일쉐이크(랜덤) 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
 CheckSort(array, N);
 return 0;
}

 

 

 

 

 

 

2. 개선 

#include <iostream>

#include <time.h>

#include <stdlib.h>

 

using namespace std; 

const int N = 10;

 

inline void swap(int a[], int i, int j){

 int t = a[i]; a[i] = a[j]; a[j] = t;

}

 

void printList(int a[]){

 int i;

 for (i = 1; i < N; i++)

  cout << a[i] << ", ";

 cout << a[i] << endl;

}

 

void CocktailShaker(int a[], int n){

 int i, start = 1, end = n; //start는 시작, end는 끝

 while(start < end) {

  for(i = start; i < end; i++)

   if(a[i] > a[i+1])

    swap(a, i, i+1);

  printList(a);

  for(i = end-1; i >= start; i--)

   if(a[i] > a[i+1])

    swap(a, i, i+1);

  printList(a);

  start++;

  end--;

  }

}

 

int main(){

  int a[N+1] = { -1, 6, 2, 8, 1, 3, 9, 4, 5, 10, 7 };

  printList(a);

  CocktailShaker(a, N);

}