qsort와 compare 완벽 이해

# qsort와 compare 완벽이해

🔷 C언어의 기본 정렬 함수: qsort

📌 qsort 정의

qsort()는 C 표준 라이브러리에서 제공하는 배열 정렬 함수입니다. 배열을 정렬하려면 배열의 시작 주소, 배열 크기, 요소 크기, 정렬 기준을 지정해야 합니다. 함수의 형태는 다음과 같습니다.

qsort(base, nitems, size, compar);

예제 코드:

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    int x = *(int*)a;
    int y = *(int*)b;
    return x - y;
}

int main() {
    int arr[] = {5, 2, 8, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, n, sizeof(int), compare);

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

🔷 qsort 인자 설명

📌 base 지정

배열의 시작 주소입니다. 배열의 첫 번째 요소의 메모리 주소를 지정합니다. 예제에서는 arr가 base입니다.

📌 nitems 지정

배열의 요소 개수입니다. 배열에 몇 개의 데이터가 있는지를 지정해야 qsort()가 그만큼만 순회합니다. 예제에서는 n에 계산해 저장합니다.

int n = sizeof(arr) / sizeof(arr[0]);

📌 size 지정

배열의 각 요소가 차지하는 메모리 크기(바이트)입니다. qsort()는 배열의 자료형을 모르므로 직접 지정해야 합니다. 예제에서는 sizeof(int)입니다.

📌 compar 지정

비교 함수 포인터입니다. 배열의 두 요소가 올바른 순서인지 아닌지를 판단하는 함수입니다. qsort()는 두 요소를 선택해 compare()에 넘기고, 반환값의 부호에 따라 두 요소를 유지하거나 바꿉니다.

🔷 compare 함수 작성과 동작 원리

compare()는 배열의 두 요소가 올바른 순서인지 판단합니다. qsort()는 두 요소의 메모리 주소를 compare()에 넘기고, 반환값의 부호를 보고 두 요소를 교환할지 유지할지를 결정합니다.

int compare(const void* a, const void* b) {
    int x = *(int*)a;
    int y = *(int*)b;
    return x - y;
}

🔷 compare 인자 의미

compare()는 두 개의 const void* 인자를 받습니다. 두 인자는 배열 안의 두 요소의 메모리 위치를 가리킵니다.

• 첫 번째 인자: 왼쪽 요소 주소 (예: 5의 주소)
• 두 번째 인자: 오른쪽 요소 주소 (예: 2의 주소)

🔷 compare 반환값 의미

compare()는 두 값의 차를 계산하여 반환합니다. 부호에 따라 qsort()가 해석하는 의미는 아래와 같습니다.

반환값	의미	동작
음수	왼쪽 값이 더 작음 (x = 2, y = 5)	순서가 맞음 → 그대로 둔다
0	두 값이 같음 (x = 3, y = 3)	순서가 맞음 → 그대로 둔다
양수	왼쪽 값이 더 큼 (x = 5, y = 2)	순서가 틀림 → 두 값을 바꾼다

🔷 양수 반환 시 교환 이유

양수는 왼쪽 값이 오른쪽 값보다 크다는 뜻입니다. 오름차순 정렬에서는 왼쪽 값이 더 작거나 같아야 하므로, 크다면 잘못된 상태입니다. qsort()는 이 잘못된 상태를 바로잡기 위해 두 요소의 위치를 바꾸어 왼쪽에 더 작은 값이 오도록 합니다. 음수나 0일 경우에는 순서가 맞기 때문에 그대로 둡니다.

🔷 구체적 예시

배열이 5, 2일 때:

• x = 5, y = 2
• x - y = 3 > 0
• 반환값이 양수 → 두 값을 바꾼다 → 결과: 2, 5

배열이 2, 5일 때:

• x = 2, y = 5
• x - y = -3 < 0
• 반환값이 음수 → 그대로 둔다

배열이 3, 3일 때:

• x = 3, y = 3
• x - y = 0
• 반환값이 0 → 그대로 둔다

🔷 요약표

단계	내용	상세 설명
1단계	기준값 선택	배열에서 하나의 요소를 기준값(pivot)으로 선택
2단계	두 요소 비교	배열 내 두 요소의 메모리 주소를 선택
3단계	compare 호출	두 요소의 주소를 compare()에 전달
4단계	compare 결과 해석	compare() 반환값에 따라 판단: • 음수 → 순서 유지 • 0 → 순서 유지 • 양수 → 두 요소 교환
5단계	배열 분할	기준값을 중심으로 작은 값과 큰 값으로 나누어 그룹 생성
6단계	재귀 호출	왼쪽 그룹과 오른쪽 그룹에 대해 같은 과정 반복
7단계	종료	더 이상 나눌 수 없을 때 정렬 완료