퀵정렬은 제곱입니다.

 

 

알고리즘 문제에서 시간 복잡도는 어떠한 문제든 반드시 고려해야 하는 중요 요소입니다. 그런데 조금 더 구체적으로 인지해야 할 것이 있습니다. 여기에서 말하는 시간 복잡도는 평균이 아니라 항상 최악의 경우를 고려해야 한다는 것입니다.

 

퀵정렬은 평균과 최악의 경우 시간 복잡도가 서로 다른 대표적인 알고리즘입니다. 거의 대부분의 케이스에서는 $\mathcal{O}(N\log{N})$의 시간 복잡도를 보이지만 최악의 경우에는 $\mathcal{O}(N^2)$으로 느리다고 배우는 버블 정렬, 선택 정렬 등과 동일한 시간 복잡도를 가집니다.

 

PS 문제에서 최악의 경우가 중요한 이유는 단 하나입니다. 단 하나의 케이스에서라도 제한 시간을 넘기면 그 코드는 시간 초과로 판정되기 때문입니다. 출제자들은 언제나 이러한 코드들이 최대한 오답을 받을 수 있게끔 데이터를 신경써서 만듭니다. 만일 이 최악의 케이스라는 것이 일반적인 방법으로 찾아내기 어렵다면 통과되는 데에 문제가 없겠지만 (실제로 해싱의 경우 최악의 경우의 시간 복잡도가 $\mathcal{O}(N^2)$이지만 저격하기 어렵기 때문에 종종 사용됩니다), 퀵정렬의 경우에는 정말, 너무나 단순한 방법으로도 저격이 가능합니다. 아니, 저격이라고 부를 것도 없는 수준의 간단한 데이터로 제곱의 시간 복잡도를 만들 수 있습니다.

 

별다른 특수 처리를 하지 않은 퀵정렬의 경우, 다음과 같은 데이터들에서 비참한 최후를 맞이하게 됩니다.

• 오름차순으로 정렬된 데이터
• 내림차순으로 정렬된 데이터
• 모든 원소가 같은 데이터

 

이와 같이 데이터가 어느 방향으로든 이미 정렬이 되어 있다면 partition을 하는 과정에서 항상 pivot이 특정 방향으로 쏠리게 되고, 이에 따라 처음 $N$개의 원소가 $N-1$개와 1개의 원소로 나누어지고, 다시 $N-1$개의 원소는 $N-2$개와 1개의 원소로 나누어지고, 다시 $N-2$개의 원소는 $N-3$개와 1개의 원소로 나누어지고...를 이어나가기 때문에 $\sum_{i=1..N}{i}=\mathcal{O}(N^2)$이 되고 맙니다.

 

이러한 문제들을 회피하는 방법에는 여러 가지가 있지만 이 글에서 다루지는 않겠습니다. 제가 추천드리고 싶은 것은 그냥 문제 풀이에 퀵정렬을 쓰지 않는 것입니다. 정렬을 직접 구현해보고 싶다면 병합 정렬이나 힙 정렬을 추천합니다. 퀵정렬을 연습해보고 싶다면 제곱의 시간 복잡도로도 통과에 무리가 없는 작은 범위의 데이터만이 주어지는 문제에만 하면 됩니다. 정렬 자체를 연습할 생각이 아니라면, 그냥 라이브러리에서 제공되는 내장 정렬 함수를 사용하기를 권장합니다.