4일차 (3)

Q5. 연습문제 Q2(204쪽)와 마찬가지로 비교, 교환 과정을 자세히 출력하는 프로그램(실습 6-3)으로 수정하세요.

내 답변:

6-3과 같이 key와 last 변수를 추가했다. 그리고 교환이 일어날 때마다 last를 업데이트 하게 했다. 그래서 해당 패스에서 교환이 일어난 가장 작은 인덱스를 저장한다. 그럼 진행중인 패스의 검사를 마쳤을 때 a[0]부터 a[last] 까지는 정렬된 상태일 것이다. 즉, 다음 패스에서 그 사이의 인덱스는 검사할 필요가 없다.

하지만 last 변수는 다음 패스에서 다시 초기화가 진행되기 때문에 패스가 끝나기 전에 key 변수에 last의 값을 대입시킨다. 그리고 매 패스는 key까지만 검사를 진행하게 된다.

void bubble(int a[], int n) {
	int i, j;
	int ccnt = 0;
	int scnt = 0;
	int key = 0;
	for (i = 0; i < n - 1; i++) {
		int last = n - 1;
		printf("패스%d:\n", i + 1);
		for (j = n - 1; j > key; j--) {
			for (int k = 0; k < n - 1; k++)
				printf("%3d %c", a[k], (k != j - 1) ? ' ' : (a[j - 1] > a[j]) ? '+' : '-');
			printf("%3d\n", a[n - 1]);
			ccnt++;
			if (a[j - 1] > a[j]) {
				scnt++;
				swap(int, a[j - 1], a[j]);
				last = j;
			}
			putchar('\n');
		}
		for (int k = 0; k < n; k++)
			printf("%3d  ", a[k]);
		putchar('\n');
		key = last;
	}
	printf("비교 %d회\n", ccnt);
	printf("교환 %d회\n", scnt);
}

 

---

정답:

///*--- 버블 정렬(버전 3) ---*/
//void bubble(int a[], int n)
//{
//	int i = 0, m;
//	int ccnt = 0;		
//	int scnt = 0;		
//	int k = 0;			/* a[k] 이전은 정렬된 상태 */
//
//	while (k < n - 1) {
//		int j;
//		int last = n - 1;					/* 마지막으로 교환한 위치 */
//
//		printf("패스%d：\n", ++i);
//		for (j = n - 1; j > k; j--) {
//			for (m = 0; m < n - 1; m++)
//				printf("%3d %c", a[m], (m != j - 1) ? ' ' :
//				(a[j - 1] > a[j]) ? '+' : '-');
//			printf("%3d\n", a[n - 1]);
//
//			ccnt++;
//			if (a[j - 1] > a[j]) {
//				swap(int, a[j - 1], a[j]);
//				last = j;
//				scnt++;
//			}
//		}
//		k = last;
//		for (m = 0; m < n; m++)
//			printf("%3d  ", a[m]);
//		putchar('\n');
//	}
//	printf("비교를 %d회 했습니다.\n", ccnt);
//	printf("교환을 %d회 했습니다.\n", scnt);
//}