[알고리즘] 정렬 알고리즘 - 칵테일 셰이커 정렬 Cocktail Shaker Sort

 

칵테일 셰이커 정렬 (Cocktail Shaker Sort) 알고리즘 : 

칵테일 셰이커 정렬(Cocktail Shaker Sort) = 양방향 버블 정렬(Bidirectional Bubble Sort) 

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

버블 정렬 의 변형. 버블 정렬과는 달리 매 패스마다 리스트의 순서를 바꿔 정렬

 

홀수 번째의 패스는 가장 작은 요소를 맨 앞으로, 짝수 번째의 패스는 가장 큰 요소를 맨 뒤로 정렬 or

홀수 번째의 패스는 가장 큰 요소를 맨 뒤로, 짝수 번째의 패스는 가장 작은 요소를 맨 앞으로 정렬

 

출처 : 위키백과

 

첫번째 패스가 완료되면 가장 작은 요소가 맨 앞으로 이동하기 때문에

두번째 패스는 맨 앞의 요소를 제외하고 앞 -> 뒤 방향으로 진행되고,

두번째 패스가 완료되면 가장 큰 요소가 맨 뒤로 이동하기 때문에

세번째 패스는 양 끝의 두 요소를 제외하고 뒤 -> 앞 방향으로 진행된다.

=> 패스가 한번씩 진행될 때 마다 정렬에서 제외되는 데이터가 양 끝에서 번갈아 하나씩 제외된다

 

 

메서드 swap() : a[idx1] 과 a[idx2] 를 교환

매개변수 : int[] a, int idx1, int idx2

 

메서드 CockTailSort() : 길이가 n인 배열 a를 칵테일 정렬

매개변수 : int[] a, int n

 

- 칵테일 정렬 :

void swap(int[] a, int idx1, int idx2) {
	int t = a[idx1];
	a[idx1] = a[idx2];
	a[idx2] = t;
}
	
void CocktailSort(int[] a, int n) {
	int i = 1;
	int l = 0;
	int r = n-1;
	int last = n-1;
	while(l != r) {
		if(i % 2 == 1) {
			for(int j = r; j > l; j--) {
				if(a[j-1] > a[j]) {
					swap(a, j-1, j);
					last = j;
				}
			}
			l = last;
		} else if (i % 2 == 0) {
			for(int j = l; j < r; j++) {
				if(a[j] > a[j+1]) {
					swap(a, j, j+1);
					last = j;
				}
			}
			r = last;
		}
		i++;
	}
}

 

 

 

 

칵테일 쉐이커 정렬 Cocktail Shaker Sort :

최선 = O(N), 평균 = 최악 = O(N^2)

안정된 정렬