1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
using namespace std;
#define MAX 1000000
 
int arr[MAX];
 
void swap(int a, int b, int arr[])
{
    int temp = 0;
 
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
int partition(int begin, int end, int arr[])
{
    int pivotIndex = (begin + end) / 2;
 
    while (begin <= end)
    {
        while (arr[begin] < arr[pivotIndex])
            begin++;
 
        while (arr[pivotIndex] < arr[end])
            end--;
 
        if (begin <= end)
        {
            swap(begin, end, arr);
            begin++;
            end--;
        }
    }
 
    return begin;
}
 
void quickSort(int begin, int end, int arr[])
{
    int rightBegin = partition(begin, end, arr);
    int leftEnd = rightBegin - 1;
 
    if (begin < leftEnd)
        quickSort(begin, leftEnd, arr);
 
    if (rightBegin < end)
        quickSort(rightBegin, end, arr);
}
 
int main()
{
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
 
    quickSort(0, n - 1, arr);
 
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << '\n';
    }
}
 
cs


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

백준 2751번을 퀵소트로 풀고 싶은데요...

좀 찾아보니까 퀵소트는 최악의 경우 O(n^2)라서 이 문제는 퀵소트로 풀 수 없는 문제라고 하더라구요.

근데 시간초과가 아니라 애초에 틀렸습니다가 떠서.....

대체 어디가 틀린건지를 모르겠습니다 ㅠ..

첨언 좀 해주시면 안 될까요 ㅠㅠ