4일차 (4)

Q6. 다음의 배열을 정렬한다고 가정하겠습니다.

{9,1,3,4,5,6,7,8}

이 배열은 두 번째 요소부터는 정렬은 되어 있지만 버전 3의 버블 정렬 알고리즘을 사용해도 빠른 시간 안에 정렬 작업을 마칠 수는 없습니다. 왜냐하면 맨 앞에 있는 요의 값(9)은 1회의 패스를 거쳐도 한 칸만 뒤로 옮겨지기 때문입니다. 그래서 홀수 번째의 패스는 가장 작은 요소를 맨 앞으로 옮기고 짝수 번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식을 사용하면 (패스의 스캔 방향을 교대로 바꾸면) 이런 정렬을 더 적은 횟수로 비교를 수행할 수 있습니다. 버전 3의 프로그램을 개선하여 양방향 버블 정렬을 수행하는 프로글매을 작성하세요.

내 답변:

우선 while문에서 for 문으로 변경했다. 진행되고 있는 패스의 숫자를 하나씩 증가하게 하고, 이를 2로 나누었을 때 몫을 확인하여 홀짝여부를 확인한다.

그리고 홀수의 경우에는 끝에서부터 검사를 진행한다. 만약 작은 숫자가 뒤에 있으면 앞으로 보낸다.

짝수의 경우에는 0부터 검사를 진행한다. 만약 큰 숫자가 앞에 있으면 뒤로 보낸다.

실습 6_3의 경우 직접 count 변수를 추가하여 확인했을 때 총 35회의 교환 및 비교를 진행하고, 다음의 코드로 진행했을 때에는 (i%2==1 비교를 제외하고) 20회의 교환과 비교를 진행하는 것을 확인할 수 있었다.

void bubble(int a[], int n) {
	int start = 0, end = n - 1, last=0;
	for(int i=0; start < end;i++){
		if (i % 2 == 1) {
			for (int j = end; j > start; j--) {
				if (a[j - 1] > a[j]) {
					swap(int, a[j - 1], a[j]);
					last = j;
				}
			}
			start = last;
		}
		else {
			for (int j = start; j < end; j++) {
				if (a[j] > a[j+1]) {
					swap(int, a[j] , a[j + 1]);
					last = j;
				}
			}
			end = last;
		}
	}
}

 

---

정답:

일단 보기에 더 깔끔하게 작성되었다. 그런데 초반 비교문(while(left < right))을 제외하더라도 25회의 비교가 일어난다. 그래서 내가 쓴 답변과 비교해보았지만 원인을 알 수가 없다... 나중에 다시 한 번 더 봐야할 것 같다.

///*--- 양방향 버블 정렬(셰이커 정렬) ---*/
//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;
//	}
//}