[알고리즘] 정렬(1) - 버블 정렬

정렬의 목적은 '탐색' => 데이터를 빠르고 쉽게 찾기 위함

버블 정렬(Bubble Sort)

물 속 깊은 곳에서 수면을 향해 올라오는 거품의 모습처럼 데이터를 정렬해서 버블 정렬이라고 불린다.

정렬 방식

• 자료구조를 순회하면서 이웃한 요소들끼리 데이터를 교환하며 정렬한다.

정렬 과정

• 해당 예제에서는 오름차순으로 한다.
• 한번의 루프가 끝나면 가장 큰 수는 맨 아래로 가기 때문에 비교 범위를 하나씩 줄인다.

1번째 루프

2번째 루프

3번째 루프

4번째 루프

 

버블 정렬의 성능

$$ 비교 횟수: (n-1)+(n-2)+...2+1 = n(n-1)/2 => O(n^{2}) $$

$$ 시간 복잡도: O(n^{2}) $$

 

코드[언어 - C]

#include <stdio.h>

int main(void)
{
    int data[] = {4,2,5,3,1};
    int length = sizeof(data) / sizeof(data[0]);
    int temp = 0;

    // 버블 정렬
    for(int i = 0; i < length; i++){
        for(int j = 0; j < length-(i+1); j++){
            if(data[j] > data[j+1]){
                temp = data[j+1];
                data[j+1] = data[j];
                data[j] = temp;
            }
        }
    }

    // 버블 정렬 출력
    for(int i = 0; i < length; i++){
        printf("%d ", data[i]);
    }
    printf("\n");

    return 0;
}

버블 정렬은 간단하지만 성능이 좋은 알고리즘은 아니다.