[예제] 퀵 정렬 구현

Problem Solving을 하다보면 주어진 원소를 정렬 시킬 필요가 있습니다.

물론 STL을 이용해서 구현할 수 있지만 해당 노트에서는 구조체 형태로 정렬하는 내용을 다룹니다.

▶ 퀵(Quick) 정렬 

상황 (조건)

특정 사람이 {나이age, 경험exp}가 있을 때,

나이가 큰 순(내림차순) / (나이가 동일한 경우) 경험이 큰 순(내림차순)

즉, 여러 기준을 적용해서 정렬하겠습니다.

 Input 

3

20 20

20 30

30 10

 

 Output 

age = 30, exp = 10

age = 20, exp = 30

age = 20, exp = 20 

 

구현 코드

#include <stdio.h>
#define MAX_NUM 100
int N;
struct Node {
    int age, exp;
    void print() {
        printf("age = %d, exp = %d\n", age, exp);
    }
}input[MAX_NUM];

bool comp(Node A, Node B) {
    if (A.age < B.age) return true;
    else if (A.age == B.age) return A.exp < B.exp;
    return 0;
}

inline void swap(Node& A, Node& B) { Node temp = A; A = B; B = temp; }
void quickSort(int first, int last) {
    register int i, j, pivot;
    if (first < last) {
        pivot = first;
        i = first, j = last;
        while (i < j) {
            while (comp(input[i], input[pivot]) && i < last) {
                i++;
            }
            while (comp(input[j], input[pivot])) {
                j--;
            }
            if (i < j) {
                swap(input[i], input[j]);
            }
        }
        swap(input[pivot], input[j]);
        quickSort(first, j - 1);
        quickSort(j + 1, last);
    }
}

int main(void) {
    freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &input[i].age, &input[i].exp);
    }
    quickSort(0, N - 1);
    // 결과 출력
    for (int i = 0; i < N; ++i) {
        input[i].print();
    }
    printf("\n");
}

 

분석

Quick Sort 혹은 다른 Sort 코드를 이용해도 상관 없습니다.

구조체를 정의하고 비교하는 부분을 comp()로 처리해서 모듈화 하였습니다.

 

comp() 함수

- 오름/내림 차순 기준에 따라 부등호 방향을 바꿔가며 디버깅하면 되기에 부등호 방향은 크게 고민할 필요 없습니다.

bool comp(Node A, Node B) {
    if (A.age < B.age) return true;
    else if (A.age == B.age) return A.exp < B.exp;
    return 0;
}

※ PS에서는 2~3가지 기준이 있기 때문에 종종 사용될 때가 있습니다.

    Quick Sort는 pivot의 위치에 따라 재귀 수행시 overflow가 날 수 있기에

    어떤 Input Case에서도 안정적인 Merge Sort를 구현하는 것을 권장합니다.

　

[실행 결과]