가장 빠른 정렬 알고리즘과 그렇게 생각하는 이유

알고리즘] 퀵 정렬(Quick Sort)에 대한 이해 (tistory.com)

알고리즘] 퀵 정렬(Quick Sort)에 대한 이해

퀵 정렬은 이름 그대로 '빠른 알고리즘'이라는 의미인데, 실제로 위 알고리즘들 중에서는 일반적으로 가장 빠른 알고리즘이라고 한다.

여기서 약간 의아할 수 있는 부분이 '병합, 힙 정렬이 최악의 경우에 퀵 정렬보다 시간 복잡도가 높은데, 어떻게 가장 빠른 알고리즘이지?'라는 생각이 들 수 있는데, 그 이유는 다음과 같다.

알고리즘을 공부를 여기까지 하는 분들이라면 모두 빅오 표기법을 알고 있을 거라고 생각한다.

그리고 빅오 표기법을 배웠을 당시 '최고차항을 제외한 나머지는 무시한다'라는 개념을 기억하고 있을 것이다.

따라서 같은 O(N)이어도 '300 * N'일 수도 있고, '100 * N'일 수도 있다는 이야기다. 

퀵 정렬은 병합 정렬과 힙 정렬보다 평균적으로 n log n에 곱해지는 수가 적어 결과적으로 평균적인 연산, 즉, 실제 연산 속도가 빠르다고 알려져 있기 때문에 병합 정렬과 퀵 정렬보다 빠르다고 알려져 있는 것이다.