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

Vitamin Quiz

---

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

풀이

---

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

/*************************************************  ** 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