baekjoon 2751

https://www.acmicpc.net/problem/2751

---

Idea

원래 정렬은Quick Sort 를 직접 구현해서 사용했지만 자꾸 시간 초과가 나왔다..

#include <stdio.h>

void quickSort(int arr[], int L, int R);

int main(void) { 
    int arr[1000001];
    int N;

    scanf("%d", &N);

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

    quickSort(arr, 0, N - 1);

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

    return 0;
}

void quickSort(int arr[], int L, int R) {
    int left = L, right = R;
    int pivot = arr[(L + R) / 2];
    int temp = 0;

    while (left <= right) {
        while (arr[left] < pivot) {
            left++;
        }
        while (arr[right] > pivot) {
            right--;
        }

        if (left <= right) {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

            left++;
            right--;
        }
    } 

    if (L < right) {
        quickSort(arr, L, right);
    }
    if (left < R) {
        quickSort(arr, left, R);
    }
}

내 코드에 문제가 있는지 언어의 한계인지 뭐가 문제인지 몰라 이것저것 다 해봤다.
다른 사람의 퀵 정렬 코드를 가져와서 써보기도 하고 언어를 바꿔서 Java 로 해보기도 했다.
결국 다 실패하고 구글링을 했는데 Quick Sort 의 한계였다. 최악의 상황엔 시간복잡도가 O(N^2)까지 발생한다고 한다.

그래서 c언어 헤더파일에 내장되어 있는 qsort 를 사용하기로 했다.

qsort 는 기본적으로 비교 함수를 내가 직접 만들어야 되는데 처음 써보는거라 다른 개발자들의 compare함수를 빌려 사용했다.

int compare (const void *a, const void *b) {
    int num1 = *(int *)a;
    int num2 = *(int *)b;

    if (num1 < num2) {
        return -1;
    }

    if (num1 > num2) {
        return 1;
    }

    return 0;
}

qsort 의 작동원리는 제대로 이해하지 못했지만 리턴값을 보고 알아서 비교하는 듯 하다.

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

뭐 그렇대요..,

---

Code

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

int compare (const void *a, const void *b);

int main(void) {
    int arr[1000001] = { 0, };
    int N;

    scanf("%d", &N);

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

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

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

    return 0;
}

int compare (const void *a, const void *b) {
    int num1 = *(int *)a;
    int num2 = *(int *)b;

    if (num1 < num2) {
        return -1;
    }

    if (num1 > num2) {
        return 1;
    }

    return 0;
}