<뇌를 자극하는 알고리즘 #5>: 버블정렬(BubbleSort) 퀴즈풀이

Vitamin Quiz

---

 문제) 버블 정렬은 이미 정렬이 되어 있어도 모든 루프를 돌며 비교를 수행하는 미련한 알고리즘이다. 정렬되어 있는 경우에는 루프를 취소하고 빠져나올 수 있도록 알고리즘을 개선하라.

풀이

---

 플래그(flag) 변수를 하나 사용함으로써 문제를 해결했다. 첫 검사에서 비교를 했는데 바꿀 것이 없었다면 플래그 값은 변함이 없을 것이다. 첫 검사로부터 데이터가 정렬이 되어 있는지를 플래그를 통해 확인한다.

/*************************************************
 ** BubbleSort Vitamin Quiz
*************************************************/

#include <stdio.h>

void BubbleSort(int dataSet[], int len)
{
	int i, j, temp;
	int flag = 0;
	for (i = 1; i < len; i++)
	{
		for (j = 0; j < len - i; j++)
		{
			if (dataSet[j] > dataSet[j + 1])
			{
				flag = 1;
				temp = dataSet[j + 1];
				dataSet[j + 1] = dataSet[j];
				dataSet[j] = temp;
			}
		}
		if (flag == 0) // 정렬할 데이터가 없었으므로 리턴
		{
			printf("정렬이 이미 되어 있습니다.\n");
			return;
		}
		flag = 0; // 다음에 정렬되는 것이 있는지 확인하기 위해 의도적으로 flag 리셋
	}
}

void main()
{
	int DataSet[] = { 6,4,2,3,1,5 };
	int Length = sizeof(DataSet) / sizeof(DataSet[0]);
	int i = 0;

	BubbleSort(DataSet, Length);
	for (i = 0; i < Length; i++)
		printf("%d ", DataSet[i]);

	printf("개선된 버블소트가 작동하는지 확인합니다.\n");
	BubbleSort(DataSet, Length);
}
/*************************************************
 ** End Line
*************************************************/

데브맷 풀이.c