오바마 대통령은 버블 소트가 비효율적이라는 정도는 안다!

오바마 대통령이 대통령 입후보 당시 상원의원일 때 구글에서 인터뷰한 화면인듯. https://youtu.be/k4RRi_ntQc8

질문: What is the most efficient way to sort a million 32 bit integers?
…
대답: I think the bubble sort would be the wrong way to go…

오바마 대통령이 대답한 bubble sort는 오름차순일 경우 집합에서 원소를 배열하여 맨 앞 두 숫자를 비교하여 작은 수를 앞에 놓고(분류), 다시 그 뒤 수와 다음 수를 비교하여 작은 수를 앞에 놓는(분류) 방식으로 집합 원소 전체를 차례로 비교하는 분류 방식이다. 간단하지만 방식이지만 집합이 클 경우 굉장히 비효율적이고 시간도 많이 소모한다.

참고로 다음은 C language로 구현해 본 bubble sort 코드다. 프로그램을 컴파일 후 실행하면 처음에 집합 범위에 해당하는 숫자를 입력하라고 하고, 집합 원소를 모두(무작위로) 입력하라고 한다. 그러고 Return을 하면 그 숫자를 모두 오름차순으로 정렬을 해서 화면에 나타낸다.

01 /* Bubble sort algorithm program in C language */
02
03 #include
04
05 int main()
06 {
07   int array[100], n, c, d, swap;
08
09   printf(“Enter number of elements\n”);
10   scanf(“%d”, &n);
11
12   printf(“Enter %d integers\n”, n);
13
14   for (c = 0; c < n; c++)
15   scanf(“%d”, &array[c]);
16
17   for (c = 0; c < (n – 1); c++)
18   {
19   for (d = 0; d < (n – c – 1); d++)
20     {
21       if (array[d] > array[d+1])
22       {
23         swap = array[d];
24         array[d] = array[d+1];
25         array[d+1] = swap;
26       }
27     }
28   }
29
30   printf(“Sorted list in ascending order:\n”);
31
32   for (c = 0; c < n; c++)
33   printf(“%d\n”, array[c]);
34
35   return 0;
36 }