퀵 정렬의 경우 worst case의 시간 복잡도는 O(N²)이다. 힙 정렬과 퀵 정렬의 best case, average case는 모두 O(NlogN)로 같지만 worst case는 힙 정렬이 O(NlogN)이고 퀵 정렬은 O(N²)이다. worst case까지 고려하여 조금이라도 더 빠른 정렬을 사용하려면 당연히 힙 정렬을 선택하는 것이 맞다.

그렇다면 왜 퀵 정렬로 업데이트되었을까?

빅오 노테이션은 대략적인 측정 방법이다. n개의 문제(보통 처리해야 할 아이템의 개수가 된다.)가 주어졌을 때 알고리즘이 실행되는 동안 수행되는 오퍼레이션을 측정하되 상수와 계수는 제거한 측정값을 말한다. 힙 정렬 와 퀵 정렬 모두 평균적으로 O(NlogN)이지만 힙 정렬에는 특별한 작업이 있다. heapify 작업이다. 정렬 작업이 수행되면서 정렬된 값이 하나 정해져서 힙에서 빠져나오게 되면 엉클어진 힙을 다시 힙 형태로 만들기 위해 힙 내의 원소들끼리 자리를 바꾸는 heapify 동작이 수행된다. 데이터의 개수가 많지 않다면 큰 영향은 없겠지만, 굉장히 큰 데이터 집합을 대상으로 힙 정렬 작업이 수행된다면 퍼포먼스 차원에서 heapify 동작은 무시할 수 없게 된다.

정렬 알고리즘에서 swap의 비중

퀵 정렬과 힙 정렬 모두 swap연산을 필요로 한다. 그렇다면 퀵 정렬과 힙 정렬의 주요 로직에서의 swap연산 횟수를 비교해보자. 퀵 정렬과 힙 정렬의 소스는 https://mgechev.github.io/javascript-algorithms 의 소스를 사용했다.

max 힙정렬의 heapify 함수

먼저 힙 정렬의 heapify 함수이다. 12~14줄에서 swap연산을 수행한다. 이 연산의 횟수를 측정한다.

퀵정렬의 partition 함수

퀵 정렬의 partition 함수이다. 이 또한 12~14줄에서 swap연산을 수행한다. 임의의 순서로 정렬된 100, 1000, 10000, 100000, 1000000 개의 엘리먼트를 갖는 배열을 대상으로 각각 30번씩 정렬 동작을 수행하여 평균을 내보았다.

힙 정렬과 퀵 정렬의 swap연산

많지 않은 엘리먼트 개수를 대상으로 하는 결과는 큰 차이가 없지만, 엘리먼트의 개수가 증가할수록 차이가 점점 더 많이 나게 된다. 크롬의 V8엔진에서 sort 함수의 구현이 힙 정렬에서 퀵 정렬로 바뀐 이유가 이 이유 때문이 아닐 수 도 있다. 하지만 개인적인 생각으로는 worst case가 힙 정렬가 퀵 정렬보다 좋다고는 하지만, 많은 데이터를 전제로 하는 상황에서는 swap연산을 무시할 수 없기에 퀵 정렬을 사용한 게 아닐까 싶다. 또한 현재 sort함수의 코드를 보면 엘리먼트의 개수에 따라 선택 정렬을 사용할지, 퀵 정렬을 사용할지 분기한다. 이렇게 세심한 성능에도 신경을 쓰고 있는 걸 보면 swap연산의 횟수 또한 힙 정렬에서 퀵 정렬로 변경한 이유 중 하나이지 않을까? 그리고 다른 언어에서도 swap연산의 횟수 때문에 기본적인 내장 정렬 함수들도 퀵 정렬 기반의 정렬 함수들이 아닐까 생각해본다.

브런치는 최신 브라우저에 최적화 되어있습니다. IE chrome safari