알고리즘 버블 정렬(Bubble Sort) C언어

▶버블 정렬(아래에 업그레이드된 버블 정렬 있음)

가장 느린 정렬 중 하나.

인접한 값의 각 쌍을 비교하여 교환하며 연속적으로 다음 쌍을 비교한다.

오름차순이라면 가장 큰 값이 배열의 끝으로 이동하며 다음 정렬 때 제외된다.

평균 성능 시간 복잡도 : O(n^2)

최악 성능 시간 복잡도 : O(n^2)

▶소스코드

void BubbleSort(int arr[], int size)
{
    int i, j, temp;
    for (i = 0; i < size - 1; i++)
    {
        for (j = 0; j < size - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

위 소스는 오름차순 정렬이다.

 

▶해석

if문에서 비교할 때 arr [j]와 arr [j+1]로 비교하므로 그냥 size로 하면 배열 자릿수가 넘어갈 수 있다.

arr [size-1]와 arr [size]를 비교할 수 없기에 size 보다 -1을 해줘야 한다.

for (i = 0; i < size - 1; i++)

 

점점 늘어나는 i 값을 이용해 size - 1에서 i 값을 뺀다. 그럼 오름차순 정렬로 가장 큰 값이 맨 뒤로 옮겨지는데 i 가 늘어나 j 가 늘어날 수 있는 최대 범위가 점차 줄어들어 차례차례 가장 큰 값들이 제외된다.

for (j = 0; j < size - 1 - i; j++)

 

오름차순이므로 앞 원소 arr [j] 보다 그다음 원소 arr [j+1]가 작으면 바꾼다.

if (arr[j] > arr[j + 1])
{
     temp = arr[j];
     arr[j] = arr[j + 1];
     arr[j + 1] = temp;
}

 

▶업그레이드된 버블 정렬

더 이상 반복해도 바뀌지 않다는 것을 인식하면 바로 종료.

거의 정렬되어 있는 배열이라면 최선의 성능이 나온다.

평균 성능 시간 복잡도 : O(n^2)

최악 성능 시간 복잡도 : O(n^2)

배열이 거의 정렬된 시간 복잡도 : O(n)

 

▶소스코드

void BubbleSort(int arr[], int size)
{
    int i, j, temp, swapped = 1;
    for (i = 0; i < size - 1 && swapped == 1; i++)
    {
        swapped = 0;
        for (j = 0; j < size - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
    }
}

 

▶해석

swapped 변수를 이용해 교환 중이라면 if문안에서 교환하고 swapped = 1을 해준다. 만약 교환을 안 한다면 swapped 은 여전히 0이 되므로 반복문을 멈추는 식을 세운다.

for (i = 0; i < size - 1 && swapped == 1; i++)

 

▶예시

#include <stdio.h>

void BubbleSort(int arr[], int size)
{
    int i, j, temp, swapped = 1;
    for (i = 0; i < size - 1 && swapped == 1; i++)
    {
        swapped = 0;
        for (j = 0; j < size - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
    }
}

int main()
{
    int arr[10] = {5, 3, 7, 6, 1, 9, 0, 2, 8, 4};

    BubbleSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

결과

0 1 2 3 4 5 6 7 8 9