13 버블 정렬, 칵테일 정렬

버블 정렬: 이웃한 두 요소의 비교, 교환을 반복해 정렬

패스(Pass): 비교, 교환 작업

버블 정렬 구현

교환 횟수는 비교 횟수 = (n - 1) + (n - 2) + 1 = n(n - 1) / 2 의 절반인 n(n - 1) / 4

swap 함수 안에서 값의 이동이 3회 발생하므로 평균 3n(n - 1) / 4

버블 정렬 개선안(1)

버블 정렬 개선안(2)

칵테일 정렬

이 배열은 맨 앞 요소(9) 때문에 빠른 시간 안에 정렬 작업을 마칠 수 없다. 

그래서 패스의 방향을 교대로 바꾸는 방식(칵테일 정렬)을 사용한다.

/*--- 양방향 버블 정렬(칵테일 셰이커 정렬) ---*/
void shaker(int a[], int n)
{
	int left = 0;
	int right = n - 1;
	int last = right;

	while (left < right) {
		int j;
		for (j = right; j > left; j--) {
			if (a[j - 1] > a[j]) {
				swap(int, a[j - 1], a[j]);
				last = j;
			}
		}
		left = last;

		for (j = left; j < right; j++) {
			if (a[j] > a[j + 1]) {
				swap(int, a[j], a[j + 1]);
				last = j;
			}
		}
		right = last;
	}
}

버블 정렬(좌), 칵테일 정렬(우)