C언어로 배우는 자료구조 [버블정렬]

버블 정렬의 이해

버블 정렬(Bobble Sort)는 인접한 두개의 원소를 비교하여 자리를 교환하는 방식으로,첫번째 원소부터 마지막 원소까지 반복하면서

가장 큰 원소가 마지막 자리에 온다. 첫 번쨰 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로

이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 해서 버블 정렬이라고 한다.

​

정렬 되지 않는 원소 [5,4,3,2,1] 을 오름차순 정렬해보자

​

1회전 [4 3 2 1 5]

2회전 [3 2 1 5 4]

3회전 [2 1 3 4 5]

4회전 [1 2 3 4 5]

​

위와 같이 정렬할수 있다.

​

버블 정렬에서 사용하는 메모리의 크기는 정렬할 원소의 개수 n이 된다. 버블 정렬에서 연산 시간이 가장 짧은 최선의 경우는

자료들이 이미 정렬되어 있는 경우이다. 이런 경우에는 i번째 원소는 n-i번 비교하게 되므로 2 / n(n-1) 가 되고 원소의

자리 교환은 발생하지 않는다.

​

버블 정렬에서 연산 시간이 가장 긴 경우는 역순으로 정렬되어 있는 경우 인데, 이 경우에도 i번째 원소는 n-i번 비교하게 되므로

전체 비교 횟수는 2 / n(n-1) 으로 같지만, 비교할 때마다 자리 교환 연산이 발생하므로 i번째 원소는 자리 교환을 n-i번하게

되어 전체 교환 횟수가 2 / n(n-1)이 된다.

#include<stdio.h>
//버블정렬 
void main(){
    int arr[10] = {9,8,7,6,5,4,3,2,1,0};
    int i,j;
    int tmp=0;
    for(i=0;i<9;i++) // 2 / n(n-1)회전 
    {
        for(j=0;j<9;j++)
        {
               if(arr[j] > arr[j+1]) //오름차순 정렬시 [j] > [j+1] 클 경우 자리교환 
               {
                  tmp = arr[j];
                  arr[j] = arr[j+1];
               arr[j+1] = tmp;
            }
        }
    }
    int k=0;
    for(k=0;k<10;k++){
        printf("[%d] ",arr[k]);
    }
}
 
결과 : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

 

위와 같은 코드로 나타낼수 있다.

​

버블 정렬은 가장 시간 복잡도가 높지만 , 가장 구현하기 쉽다는 장점이 있다 간단한 프로그램을 개발한다면 굳이 퀵 정렬과 같은

복잡한 알고리즘을 구현해서 사용할 필요는 없을것 같다. 내 메모리는 16기가 이니까..