[C언어 퀵 정렬 알고리즘] 퀵 정렬 구현하기

💡 이번에는 퀵 정렬 하는 법을 배워보았다.

문제

💡 사용자가 입력한 값이 오름차순으로 퀵 정렬 되게 코드를 구현하시오

당연히 없는 문제기에 대충 내가 만들었다.

해답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 1000

int a [SIZE];

int swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quickSort(int start, int end) {
    if (start >= end) {
        return;
    }
    int key = start;
    int i = start + 1;
    int j = end;
    int temp;

    while (i <= j) {

        while (i <= end && a[i] <= a[key]) {
            i++;
        }

        while (j > start && a[j] >= a[key]) {
            j--;
        }

        if (i > j) {
            swap(&a[key], &a[j]);
        } else {
            swap(&a[i], &a[j]);
        }
    }

    quickSort(start, j - i);
    quickSort(j + 1, end);
}

int main(void) {
    int n;
    scanf("%d", &n);

    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &a[i]);
    }

    quickSort(0, n - 1);

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

    return 0;
}

설명

[C언어 선택정렬 알고리즘] 선택정렬 구현하기 와 [C언어 선택정렬 알고리즘] 삽입정렬 구현하기 에서 도대체 main 에서 n 이 무엇인지 모르겠다고 썼었는데 이제야 깨달았다.

들어갈 원소의 개수를 써주는 것이었다. (근데 안 써주고 다른 값 써도 잘 돌아가던데..?)

quick 정렬이란?

피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다.

값을 서로 교체하는 데에 $N$번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 $logN$번이 소요되므로 평균적으로 𝜃(𝑁𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다.

5(피벗)4389671102

5(피벗)	4	3	2	9	6	7	1	10	8
5(피벗)	4	3	2	1	6	7	9	10	8
5(피벗)	4	3	2	1	6	7	9	10	8

마지막 표에서 6의 오른쪽 값에는 정렬할 것이 없고, 1과 엇갈리게 된다.

그래서 여기서 전체 원소를 나누게 된다.

1(피벗)43256(피벗)79108

원소를 절반씩 나눌 때 𝑙𝑜𝑔𝑁의 시간 복잡도가 나오는 대표적인 예시는 완전 이진 트리이며 완전 이진 트리는 컴퓨터 공학에서 가장 선호하는 이상적인 형태이다.

swap 함수

int swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

이 함수는 삽입정렬과 선택정렬에서 썼던 것 처럼 그 이외에도 아주 많이 쓰이는 곳이 많다.

swap 함수 정도는 외위두는 것이 좋을 것 같다.

quickSort 함수

void quickSort(int start, int end) {
    if (start >= end) {  // 시작과 끝이 같은 값이면 정렬 할 필요가 없다.
        return;
    }

    int key = start;    // 피벗값을 부분배열의 첫번째 원소가 되도록 만들어준다.
    int i = start + 1;  // 왼쪽에서 출발(피벗값의 하나 오른쪽 값부터 출발)
    int j = end;    // 오른쪽에서 출발
    int temp;

    while (i <= j) { // 엇갈릴 떄까지 반복한다. i가 j보다 커졌을 때는 엇갈린 순간이기 때문이다.

        while (i <= end && a[i] <= a[key]) {  
						// 왼쪽에서 출발한 i가 end보다 작거나 같거나 a[i]가 a[key] 보다 작고 같으면 오른쪽으로 이동
            i++;
        }

        while (j > start && a[j] >= a[key]) {
						// 오른쪽에서 출발한 j가 start 크고 a[j]가 a[key]보다 크거나 같으면 왼쪽으로 이동
            j--;
        }

        // i와 j가 엇갈린 상태라면 스왑
        if (i > j) {
            swap(&a[key], &a[j]);
        } else {
            swap(&a[i], &a[j]);
        }
    }

    // 재귀적으로 두번 호출하게 만듦
    quickSort(start, j - i);
    quickSort(j + 1, end);
}

솔직히 이해하자면 이해 할 만한 코드인데 하나 하나 찍어보면서 왜 재귀적으로 두 번 호출하는 것인지 등을 더 상세하게 알았으면 좋았겠다 싶다.

그러지 않았던 이유는 시간적인 문제도 있었고, 어디에 어떻게 찍어야 될지도 모르겠고…

코드를 봤을 때 quickSort(start, j - i); 은 왼쪽을 다시 정렬하는 것이고 quickSort(j + 1, end); 은 오른쪽을 다시 정렬하는 코드 같은데 j 의 역할이 궁금하다.

main 함수

int main(void) {
    int n;
    scanf("%d", &n);    // 원소의 개수가 다섯개인 것을 알려주는 것이다.

    for (int i = 0 ; i < n ; i++) { // a에 값을 넣어준다.
        scanf("%d", &a[i]);
    }

    quickSort(0, n - 1); // 인덱스는 0부터이기 때문에 n - 1 해준다.

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

    return 0;
}

---

마치며..

회사에서는 재귀함수를 써본 적이 없어서 그 부분에서 헷갈리는 것 같다.

진짜 설명 조금만 더 해주셨으면..허허..