COS Pro 2급 C 언어: 50.1 거품 정렬 구현하기

50 배열 정렬하기

프로그래밍을 하다 보면 수많은 값들을 처리하게 됩니다. 보통 특별한 순서 없이 섞여있는 값들은 오름차순이나 내림차순으로 정렬해야 할 경우가 많습니다. 특히 정렬은 매우 중요한 문제라서 정렬을 빠르고 효율적으로 처리하기 위한 알고리즘들이 다양하게 나와있습니다.

이번에는 정렬 알고리즘 중에서 가장 간단한 알고리즘인 거품 정렬(bubble sort)을 구현해보고, C 언어에서 제공하는 퀵 정렬(quick sort) 함수 사용 방법을 알아보겠습니다.

50.1 거품 정렬 구현하기

1부터 10까지의 숫자가 무작위로 들어있는 배열을 거품 정렬 알고리즘으로 정렬해보겠습니다. 다음 내용을 소스 코드 편집 창에 입력한 뒤 실행해보세요.

bubble_sort.c

#include <stdio.h>

void bubble_sort(int arr[], int count)    // 매개변수로 정렬할 배열과 요소의 개수를 받음
{
    int temp;

    for (int i = 0; i < count; i++)    // 요소의 개수만큼 반복
    {
        for (int j = 0; j < count - 1; j++)   // 요소의 개수 - 1만큼 반복
        {
            if (arr[j] > arr[j + 1])          // 현재 요소의 값과 다음 요소의 값을 비교하여
            {                                 // 큰 값을
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;            // 다음 요소로 보냄
            }
        }
    }
}

int main()
{
    int numArr[10] = { 8, 4, 2, 5, 3, 7, 10, 1, 6, 9 };   // 정렬되지 않은 배열
 
    bubble_sort(numArr, sizeof(numArr) / sizeof(int));    // 거품 정렬 함수 호출

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", numArr[i]);    // 1 2 3 4 5 6 7 8 9 10
    }

    printf("\n");

    return 0;
}

실행 결과

1 2 3 4 5 6 7 8 9 10

거품 정렬 알고리즘의 규칙은 다음과 같습니다.

처음부터 끝까지 요소를 순회하면서 모든 요소를 비교
현재 값과 다음 값을 비교하여 큰 값을 다음으로 보냄(오름차순)

이제 bubble_sort 함수를 살펴보겠습니다. bubble_sort 함수는 int arr[]과 같이 정렬할 배열을 매개변수로 받습니다. 또한, 매개변수 arr[]로는 요소의 개수를 모르니 요소의 개수도 함께 받습니다.

void bubble_sort(int arr[], int count)    // 매개변수로 정렬할 배열과 요소의 개수를 받음

for 반복문으로 배열을 처음부터 끝까지 순회합니다. 이때 요소 하나를 반복할 때마다 다시 처음부터 끝 - 1까지, 즉, 0부터 count - 1까지 반복합니다. 여기서 -1을 하는 이유는 현재 값과 다음 값을 비교할 때 맨 마지막 요소는 배열의 인덱스를 벗어난 값과 비교하게 됩니다. 따라서 배열의 인덱스를 벗어나지 않도록 마지막 요소의 바로 앞에서 반복을 끝냅니다.

for (int i = 0; i < count; i++)    // 요소의 개수만큼 반복
{
    for (int j = 0; j < count - 1; j++)   // 요소의 개수 - 1만큼 반복
    {

현재값 arr[j]와 그다음에 있는 값 arr[j + 1]을 비교하여 큰 값을 다음 요소로 보냅니다. 즉, 작은 값이 먼저 오는 오름차순(ascending) 정렬입니다. 부등호를 반대로 해주면 내림차순(descending)이 되겠죠? 여기서 큰 값을 다음 요소로 보낼 때는 기존 값을 임시 변수 temp에 저장해놓고 다음 요소에 있는 값을 가져온 뒤 temp의 값을 다음 요소에 저장해서 값을 서로 바꿉니다. 이를 자리 바꾸기(swap)라 합니다.

if (arr[j] > arr[j + 1])          // 현재 요소의 값과 다음 요소의 값을 비교하여
{                                 // 큰 값을
    temp = arr[j];       
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;            // 다음 요소로 보냄
}

이제 정렬되지 않은 배열 numArr을 bubble_sort 함수에 넣은 뒤 printf로 각 요소를 출력해보면 배열이 1부터 10까지 순서대로 정렬된 것을 볼 수 있습니다.

int main()
{
    int numArr[10] = { 8, 4, 2, 5, 3, 7, 10, 1, 6, 9 };   // 정렬되지 않은 배열
 
    bubble_sort(numArr, sizeof(numArr) / sizeof(int));    // 거품 정렬 함수 호출

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", numArr[i]);    // 1 2 3 4 5 6 7 8 9 10
    }

    printf("\n");

    return 0;
}

여기서 설명한 거품 정렬은 이해를 돕기 위해 최적화를 하지 않고 간단하게 구현했습니다. 좀 더 효율적으로 정렬하려면 이미 정렬된 맨 마지막 원소는 건너뛰어도 됩니다. 여러분들이 한 번 최적화해서 구현해보기 바랍니다.

거품 정렬은 요소 개수 * 요소 개수(n²)로 비교하기 때문에 효율이 좋지 않습니다. 정렬 알고리즘은 여러 개가 있는데 그 중에서 퀵 정렬이 효율이 좋아서 널리 쓰이며 C 언어 표준 함수에도 포함되어 있습니다.

내비게이션 생략