버블 정렬

버블정렬(bubble sort)이란?교환정렬이라고도 하며 정렬이 진행되는 모양이 비누거품(bubble)과 같다고 하여 붙여진 이름이다. 나란히 있는 두개의 데이터를 계속하여 바꾸어 나간다.

버블정렬 과정
1. 우선 맨 처음에 모든 원소들의 최대값을 찾으려면 맨 처음 원소와 둘째 원소를 비교한다. 만약 앞
   의 원소가 뒤의 원소보다 크면 두 원소의 자리를 바꾼다.
2. 둘째 원소와 셋째 원소를 비교해 자리를 바꾼다.
3. 이 과정을 마지막 원소까지 반복하면 맨 마지막 자리에 제일 큰 원소가 자리잡게 된다.4. 최대값을 가진 원소를 제외하고 나머지에 대해서 이 과정을 반복하면 그 다음으로 큰 원소를 찾
  아내 마지막에서 둘째 자리에 넣게 된다.5. 과정을 끝까지 반복하면 모든 원소가 오름차순으로 정리된다.

아래는 기본적인 버블정렬의 소스코드이다.

void Bubble(int item[], int count)
{
        register int i, j, temp;
        for(i=0; i<count-1; i++) {
                for(j=0; j<count-i-1; j++) {
                        // 오름차순이 되게 비교를 하여 데이터 교환
                        if(item[j] > item[j+1]) {
                                temp = item[j];
                                item[j] = item[j+1];
                                item[j+1] = temp;
                        }
                }
        }
}

버블 정렬의 예와 각 단계 진행 과정

/* list에 대한 기본 버블정렬 알고리즘 */
void bubble_sort(element list[], int n)
{
     int i, j;
     element next;
     for(i = n-1; i > 0; i--)
     { /*1*/
          for(j = 0; j < i; j++)
         { /*2*/
               if(list[j] > list[j + 1]
               { /*3*/
                   swap(list[j], list[j + 1]);
               }
          }
     }
}

데이터  15 4 8 3 50 9 20
1단계    4 8 3 15 9 20 50 2단계    4 3 8 9 15 20 50
3단계    3 4 8 9 15 20 50
4단계    3 4 8 9 15 20 50

1 단계 list[i]와 list[i+1]를 i = 0,1,2, ···, n-2에 대하여 비교하여 만약 뒤 데이터가 값이 더 작으면 바꾼다
(swap list[i]와 list[i+1]) 이 과정을 거치면 가장 큰 값이 맨 뒤로 이동한다.
2 단계 list[i]와 list[i+1]를 i = 0,1,2, ···, n-3에 대하여 비교하여 만약 뒤 데이터가 값이 더 작으면 바꾼다
(swap list[i]와 list[i+1]) 이 과정을 거치면 두 번째 큰 값이 뒤에서 두 번째에 위치한다.
3 단계 list[i]와 list[i+1]를 i = 0,1,2, ···, n-4에 대하여 비교하여 만약 뒤 데이터가 값이 더 작으면 바꾼다
(swap list[i]와 list[i+1]) 이 과정을 거치면 세 번째 큰 값이 뒤에서 세 번째에 위치한다.
n-1단계list[i]와 list[i+1]를 i = 0에 대하여 비교하여 만약 뒤 데이터가 값이 더 작으면 바꾼다
(swap list[i]와 list[i+1]) 이 과정을 거치면 n-1번째 큰 값이 뒤에서 n-1번째에 위치한다.

버블정렬 프로그램의 분석

단계	첨자변화	비교횟수
1단계	i=n-1 : j=0,1,2,…,n-2	n-1번
2단계	i=n-2 : j=0,1,2,…,n-3	n-2번
3단계	i=n-3 : j=0,1,2,…,n-4	n-3번
... ...
n-2단계	i=2 : j=1,0	2번
n-1단계	i=1 : j=0	1번

따라서 정렬을 하기위한 전체 비교횟수 T(n) = n(n-1)/2 이다.
비교 횟수로 따지면 수행시간 복잡도는 O(n(n-1)/2 ) = O(n의 거듭제곱)이다.
n에 관한 2차 함수로 프로그램 수행 시간이 걸린다.