C Data Structure - 버블 정렬

버블 정렬을 학습 후에 바로 정리한다.

버블 정렬이란?

위와 같은 4칸 크기의 배열 구조가 존재하고 그 안에 값이 정렬되지 않은 채로 존재한다. 여기서 우리는 오름차순으로 값을 정렬하고자 한다.

각 화살표 시작에 적힌 원 숫자 순서대로 값을 결정하는 방법이다. 어떻게? 인덱스를 하나씩 증가시켜가면서 인덱스와 뒤 인덱스를 비교하여 값의 위치를 조정하는 것. 그것이 버블 정렬이다.

총 4개의 값이 들어왔다고 가정.

3번째 자리, 2번째 자리, 1번째 자리, 0번째 자리 순으로 값이 정해져야 한다.

(1) 3번째 자리에 들어올 값을 정하기 위해서는 [0]과 [1](0+1)을 비교, [1]과 [2](1+1)를 비교, [2]와 [3](2+1)을 비교 ( 3번 반복 ) -> 3번째 자리에 들어올 값 결정

(2) 2번째 자리에 들어올 값을 정하기 위해서는 [0]과 [1](0+1)을 비교, [1]과 [2](1+1)를 비교 ( 2번 반복 ) -> 2번째 자리에 들어올 값 결정
(3) 1번째 자리에 들어올 값을 정하기 위해서는 [0]과 [1](0+1)을 비교 ( 1번 반복 ) -> 1번째 자리에 들어올 값 결정
(4) 0번째 자리에 들어올 값은 자연스럽게 결정

결국 총 3번 반복하는데 그 반복 하나하나마다 3번, 2번, 1번 반복을 해야한다.
이를 코드로 나타낸다면

for ( ... )
{
    for( ... )
    {
        ...
    }
}

이러한 형태가 되는 것이다.

코드 구현 및 실행 결과

----

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

i의 역할은 j가 어느 값까지만 접근 가능한지를 결정해주며, j는 i의 제한만큼만 순회하면서 각 i에 해당하는 최대 j값 + 1 번째 인덱스를 가장 큰 값으로 세팅해놓는다.

----

 

버블 정렬 성능

최악의 경우 비교 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)
최악의 경우 대입 횟수 : 비교 후 바로 대입이 진행되므로 O(n^2), temp 연산으로 인한 *3 -> 3 * O(n^2) -> O(n^2)