65. 배열 정렬

1. 키워드

버블 정렬(Bubble Sort)
퀵 정렬(Quick Sort)
스왑(Swap)
qsort(Quick Sort)

2. 배열 정렬하기

이번에는 정렬 알고리즘 중에서 가장 간단한 알고리즘인 버블 정렬을 구현해 보고, C에서 제공하는 퀵 정렬 함수 사용 방법을 알아보자.

3. 버블 정렬 구현하기

1부터 10까지 숫자가 무작위로 들어있는 배열을 버블 정렬 알고리즘으로 정렬해 보자.

#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]);
    }

    printf("\n");

    return 0;
}

// 1 2 3 4 5 6 7 8 9 10

버블 정렬 알고리즘의 규칙은 다음과 같다.

1] 처음부터 끝까지 요소를 순회하면서 모든 요소를 비교

2] 현재 값과 다음 값을 비교하여 큰 값을 다음으로 보냄(오름차순)

이제 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]을 비교하여 큰 값을 다음 요소로 보낸다.
즉, 작은 값이 먼저 오는 오름차순 정렬이다.
부등호를 반대로 해주면 내림차순이 된다.
여기서 큰 값을 다음 요소로 보낼 때는 기존 값을 임시 변수 temp에 저장해놓고 다음 요소에 있는 값을 가져온 뒤 temp의 값을 다음 요소에 저장해서 값을 서로 바꾼다.
이를 스왑이라 한다.

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]);
    }

    printf("\n");

    return 0;
}

4. 퀵 정렬 함수 사용하기

퀵 정렬 함수 qsort에는 정렬할 배열 또는 메모리의 주소, 요소 개수, 요소 크기, 비교 함수를 넣어준다.

qsort(정렬할배열, 요소개수, 요소크기, 비교함수);
qsort(정렬할메모리주소, 요소개수, 요소크기, 비교함수);

실제로 정렬을 한다면 정렬할 배열의 자료형도 제각각이고 비교 방식도 여러 가지이므로 비교 함수는 우리가 구현해서 함수의 메모리 주소(함수 포인터)를 넣어주게 된다.

#include <stdio.h>
#include <stdlib.h> // qsort 함수가 선언된 헤더 파일

int compare(const void *a, const void *b) // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a; // void 타입 포인터를 int 타입 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b; // void 타입 포인터를 int 타입 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 < num2) // a가 b보다 작을 때는
        return -1;   // -1 반환

    if (num1 > num2) // a가 b보다 클 때는
        return 1;    // 1 반환

    return 0; // a와 b가 같을 때는 0 반환
}

int main()
{
    int numArr[10] = {8, 4, 2, 5, 3, 7, 10, 1, 6, 9}; // 정렬되지 않은 배열

    // 정렬할 배열, 요소 개수, 요소 크기, 비교 함수를 넣어줌
    qsort(numArr, sizeof(numArr) / sizeof(int), sizeof(int), compare);

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

    printf("\n");

    return 0;
}

// 1 2 3 4 5 6 7 8 9 10

먼저 qsort 함수를 사용하기 전에 비교 함수 compare를 만들어야 한다.
다음은 오름차순 정렬 조건이다.

1] a < b일 때는 -1을 반환

2] a > b일 때는 1을 반환

3] a == b일 때는 0을 반환

이건 qsort를 사용하기 위한 약속이다.
만약 a < b일 때 1을 반환하면 반대로 내림차순 정렬이 된다.

비교 함수를 정의할 때는 반드시 int 타입 반환값과 const void 타입 포인터 매개변수가 두 개 있어야 한다.
하지만 const void 타입 포인터로는 값을 비교할 수 없으므로 정렬할 배열의 자료형에 따라 const void 타입 포인터를 변환한 뒤 역참조하여 값을 가져온다.
여기서는 정렬할 배열이 int 타입이므로 const void 타입 포인터를 int 타입 포인터로 변환한 뒤 역참조하여 값을 가져왔다.
값을 가져온 뒤에는 각 값을 비교하여 -1, 1, 0을 반환한다.

int compare(const void *a, const void *b) // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a; // void 타입 포인터를 int 타입 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b; // void 타입 포인터를 int 타입 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 < num2) // a가 b보다 작을 때는
        return -1;   // -1 반환

    if (num1 > num2) // a가 b보다 클 때는
        return 1;    // 1 반환

    return 0; // a와 b가 같을 때는 0 반환
}

const void *

const void *는 void 타입 상수를 가리키는 포인터라는 뜻이다.
즉, qsort 함수를 통해 compare 함수가 포인터를 전달 받았을 때 포인터가 가리키는 값이 상수이다.
따라서 compare 함수 안에서는 값을 임의로 변경해서는 안 된다.

이제 qsort 함수를 호출한다.
qsort 함수에 정렬할 배열, 요소 개수, 요소 크기, 비교 함수를 넣어준다.
요소 크기는 sizeof로 구하면 되고, 비교 함수는 ()(괄호)를 붙이지 않은 함수 포인터를 넣는다.

int numArr[10] = {8, 4, 2, 5, 3, 7, 10, 1, 6, 9}; // 정렬되지 않은 배열

// 정렬할 배열, 요소 개수, 요소 크기, 비교 함수를 넣어줌
qsort(numArr, sizeof(numArr) / sizeof(int), sizeof(int), compare);

printf로 각 요소를 출력해 보면 1부터 10까지 순서대로 정렬된 것을 볼 수 있다.

내림차순

내림차순 비교 함수는 오름차순에서 부등호만 반대로 바꾸면 된다.

1] a > b일 때는 -1을 반환

2] a < b일 때는 1을 반환

3] a == b일 때는 0을 반환

int compare(const void *a, const void *b) // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a; // void 타입 포인터를 int 타입 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b; // void 타입 포인터를 int 타입 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 > num2) // a가 b보다 클 때는
        return -1;   // -1 반환

    if (num1 < num2) // a가 b보다 작을 때는
        return 1;    // 1 반환

    return 0; // a와 b가 같을 때는 0 반환
}

오름차순과 내림차순을 좀 더 간단하게 구현하려면 다음과 같이 매개변수를 뺀 값을 반환하면 된다.

int compare(const void *a, const void *b)
{
    return *(int *)a - *(int *)b; // 오름차순
}

int compare(const void *a, const void *b)
{
    return *(int *)b - *(int *)a; // 내림차순
}

즉, 값을 반환할 때 반드시 -1, 1, 0일 필요는 없다.
값이 같을 때만 0이면 되고, 값이 크거나 작을 때는 음수와 양수를 반환하면 된다.

65. 배열 정렬

1. 키워드

2. 배열 정렬하기

3. 버블 정렬 구현하기

4. 퀵 정렬 함수 사용하기

References