[C언어] 백준 2751 : 수 정렬하기 2

내가 이해한 문제

1. 정렬 방법들을 잘 몰랐기에 빠르게 정렬 할 수 있는 방법들을 검색했다.

2. 일반적인 상황에서, 퀵 정렬이 엄청 빠르고, 병합정렬, 힙정렬 등등이 있다고 했다.

3. 퀵 정렬을 사용해보고 싶었다.

내가 푼 방법 (틀림)

#include <stdio.h>

void ft_quicksort(int arr[], int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int pivot = left;
    int i = pivot + 1, j = right;
    int temp;
    while (i <= j)
    {
        while (arr[i] <= arr[pivot] && i <= right)
        {
            i++;
        }
        while (arr[j] >= arr[pivot] && j > left)
        {
            j--;
        }
        if (i > j)
        {
            temp = arr[j];
            arr[j] = arr[pivot];
            arr[pivot] = temp;
        }
        else
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    ft_quicksort(arr, left, j - 1);
    ft_quicksort(arr, j + 1, right);
}

int main()
{
    int i, n;
    scanf("%d", &n);
    int arr[n];
    i = 0;
    while (i < n)
    {
        scanf("%d", &arr[i]);
        i++;
    }
    ft_quicksort(arr, 0, n - 1);
    i = 0;
    while (i < n)
    {
        printf("%d\n", arr[i]);
        i++;
    }
}

약 4시간정도 시간 갈았는데 시간초과가 떴다.
퀵정렬이 일반적으로 빠른 건 맞지만, 최악의 경우 O(n^2)의 시간이 걸리는데 이 경우가 걸린 것 같다.

시간을 너무 많이 투자해서 병합이든 힙이든 지금 할 맘이 없다. 나중에 사용해야 될 때가 오면 그때 다시 공부할 것 같다.

결국 구글링으로 언어에 내장된 퀵정렬을 사용해서 답을 제출했다.

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

int num[1000001] = {
    0,
};

int compare(const void *a, const void *b)
{
    if (*(int *)a > *(int *)b)
        return 1;
    else if (*(int *)a < *(int *)b)
        return -1;
    else
        return 0;
}

int main()
{
    int n;

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &num[i]);
    qsort(num, n, sizeof(int), compare);

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

퀵 정렬 내장함수 이해

#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]); // 1 2 3 4 5 6 7 8 9 10
    }

    printf("\n");

    return 0;
}
https://dojang.io/mod/page/view.php?id=638

https://mjeong9316.tistory.com/170 -> 내장함수 사용해서 제출

https://spacebike.tistory.com/29 -> 퀵 정렬의 쉬운 이해
https://code-lab1.tistory.com/23 -> 퀵 정렬의 쉬운 이해2

https://hongku.tistory.com/149 -> 퀵 정렬 제출 전 참고한 사이트
https://prosto.tistory.com/177 -> 퀵 정렬 제출 전 참고한 사이트2