퀵 정렬을 이용해 수를 정렬하는 문제
문제 링크

#include <iostream>
#include <algorithm>
#include <random>
#define MAX 1000001

using namespace std;

int N;
int arr[MAX];

void quick_sort(int start, int end)
{
    int pivot = arr[start];
    int left = start+1;
    int right = end;

    if(start >= end) return;

    while(1)
    {
        while (left <= right && arr[left] <= pivot)
        {
            left++;
        }
        while (left <= right &&  arr[right] >= pivot)
        {
            right--;
        }
        if(left > right) break;
        swap(arr[left], arr[right]);
    }

    // 위 반복문 마지막에 left와 right가 ++ 되어 위치가 역전되었으므로 start와 right의 원소를 바꿔줌
    swap(arr[start], arr[right]);
    // pivod(start->right)은 제 위치에 있으므로 pivot을 제외한 왼쪽 배열과 오른쪽 배열을 각각 다시 퀵 정렬
    quick_sort(start, right-1); 
    quick_sort(right+1, end);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    // 배열 랜덤으로 섞기
    random_device rd;
    mt19937 g(rd());
    shuffle(arr, arr+N, g);

    quick_sort(0, N-1);

    for (int i = 0; i < N; i++)
    {
        cout << arr[i] << "\n";
    }

    return 0;
}

🔥 error

vscode 상으로는 잘 출력되지만 백준 문제에서는 시간제한 때문에 O(nlogn) 가 되어야 정답처리 되었다. (시간초과)

퀵 정렬의 최악의 경우는 순서대로 정렬되어있거나, 거꾸로 정렬되어 있는 경우, 시간 복잡도는 O(n^2) 이다.

shuffle()

따라서 위 코드에서

	#include <random>
    
    // 배열 랜덤으로 섞기
    random_device rd;
    mt19937 g(rd());
    shuffle(arr, arr+N, g);

퀵 정렬을 하기 전, 배열을 랜덤으로 섞어 퀵 정렬의 최악의 경우가 되지 않도록 해줬다.

헤더 #include < random > 선언과
shuffle()의 인자인 g를 정의하는 과정이 필요하다.

random_shuffle()

참고로 shuffle() 보다 더 편리한 random_shuffle() 함수가 있었지만 c++14까지만 지원을 했고 c++17에서는 지원을 하지 않나 쓸 수 없었다.

sort()

사실 c++ std 에서 지원하는 sort() 함수는 퀵 정렬, 힙 정렬, 삽입 정렬을 혼합해서 사용하는 인트로 정렬로 구현되어 있어, 최악의 경우에도 O(nlogn)이므로 sort()을 쓰는 것이 정신 건강에 좋지만 퀵 정렬을 익히기 위해 퀵 정렬로 풀어봤다.

References

https://congcoding.tistory.com/62
https://torbjorn.tistory.com/65