[C] 버블 정렬 알고리즘 Bubble Sorting Algorithm

#1. 버블 정렬이란?

버블정렬 알고리즘의 시각화 (wikipedia)

버블 정렬은 정렬할 요소 목록을 반복적으로 살펴보고 인접한 요소를 비교하고 순서가 잘못된 경우 교환하는 간단한 정렬 알고리즘이에요. 작은 요소가 목록의 맨 위로 점차 버블링되기 때문에 버블 정렬이라고 합니다. 

버블 정렬은 평균 및 최악의 경우 시간 복잡도가 O(n^2)(여기서 n은 정렬할 요소 수)이기 때문에 특히 큰 목록의 경우 효율적인 정렬 알고리즘으로 간주되지 않아요. 그러나 이해하고 구현하기 쉽기 때문에 작거나 거의 정렬된 목록에 유용하게 쓰여요.

 

#2. 버블 정렬의 예시

다음과 같은 정렬되지 않은 배열이 있다고 가정해요. 프로그램은 이 배열을 오름차순으로 정렬해야 해요.

[7,2,0,1,5,6,4]

알고리즘은 배열의 첫 두 숫자(7,2)를 비교해요.

7 > 2 로 정렬되지 않았으니 두 수를 바꾸어요.

[2,7,0,1,5,6,4]

이를 배열의 처음부터 끝까지 작업한다면 이렇게 되어요.

[2,0,1,5,6,4,7] <1회>

가장 큰 수인 7 이 정렬 되었어요. 이를 여러 번 반복한다면 다음과 같이 진행돼요.

[0,1,2,5,4,6,7] <2회>

[0,1,2,4,5,6,7] <3회>

[0,1,2,4,5,6,7] <4회>

<3회> 부터 <4회> 까지는 아무 변화가 없으니 모두 정렬된 것으로 정의해요.

 

#3.  예제 코드

#include <stdio.h>

// 배열을 입력받아 버블정렬하는 함수
void bubbleSort(int arr[], int size) 
{
    int temp, i, j;
    int swapped = 1;
    
    // swapped 변수가 1인 동안 반복
    while (swapped) 
    {
        swapped = 0;
        i = 0;

        // i번째 요소와 i+1번째 요소를 비교하여 큰 값을 뒤로 보내기 위한 반복문
        while (i < size - 1) 
        {
            j = i + 1;

            // j번째 요소와 j+1번째 요소를 비교하여 큰 값을 뒤로 보내기 위한 반복문
            while (j < size) 
            {
                if (arr[i] > arr[j]) 
                {
                    // arr[i]와 arr[j]의 위치를 바꾸기 위해 temp 변수를 사용
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    swapped = 1;
                }
                j++;
            }
            i++;
        }
    }
}

int main() 
{
    int arr[] = {5, 2, 8, 6, 1, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("정렬 전: ");
    for (int i = 0; i < size; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    bubbleSort(arr, size);
    
    printf("정렬 후: ");
    for (int i = 0; i < size; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}