버블 정렬(Bubble Sort)

버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식입니다. 두 데이터를 비교하여, 정렬순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔나갑니다. 정렬의 우선순위가 가장 낮은 제일 큰 값을 맨 뒤로 보내기. 앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 이름 지어진 것입니다. for문에 대한 반복 조건의 정확한 이해가 필요합니다.

#include <stdio.h>
 
void BubbleSort(int arr[], int n) {
    int i, j;
    int temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < (n - i) - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
 
int main(void) {
    int arr[4] = { 3,2,4,1 };
    int i;
 
    BubbleSort(arr, sizeof(arr) / sizeof(int));
    for (i = 0; i < 4; i++)
        printf("%d ", arr[i]);
 
    printf("\n");
    return 0;
}

버블 정렬의 성능 평가를 위해서 비교의 횟수를 가지고 판단합니다. 두 데이터간의 비교 연산 횟수 입니다. 버블 정렬의 비교횟수는 이중 for 문안에 위치한 if문의 실행 횟수를 기준으로 계산할 수 있습니다. 이렇듯 버블 정렬에서 데이터의 수가 n개일 대 진행되는 비교의 횟수는 (n-1) + (n-2) + (n-3) ... + 2 + 1 입니다. 그리고 이는 n(n-1)/2 = (n^2-n2)/2 가 됩니다. 따라서 빅오는 O(n^2)이 됩니다. 이동의 횟수로도 판단할 수 있습니다. 위치를 변경을 위한 데이터의 이동횟수를 말하는데요. 정렬기준의 역순으로 저장된 상태라면 비교의 횟수와 이동의 횟수가 일치하기 때문에 최악의 경우를 기준으로 하여 O(n^2)입니다.