퀵 정렬 vs 힙 정렬
자바스크립트의 sort 함수는 배열 오브젝트의 내장 함수이다. 이 sort 함수의 내부 구조는 우리가 흔히 알고 있는 정렬 알고리즘이 구현되어 있다. 크롬의 v8엔진 코드를 보면 그 내부 구현부를 확인할 수 있다.
먼저 과거 크롬 브라우저부터 확인해보자. v8 engine의 array.js 코드를 보면 정렬 알고리즘을 찾을 수 있다. 초기 크롬은 힙 정렬로 구현되어 있다.
https://github.com/v8/v8/blob/43d26ecc3563a46f62a0224030667c8f8f3f6ceb/src/array.js#L648-L724
힙 정렬은 좋은 알고리즘이다. 현재 가장 이상적으로 사용할 수 있는 정렬 알고리즘의 시간 복잡도는 O(NlogN)이다. 그중 worst case 또한 O(NlogN)의 성능을 내는 힙 정렬이다.
그런데 이 알고리즘은 얼마 지나지 않아 퀵 정렬로 업데이트되었다.
https://github.com/v8/v8/blob/950d2051a5ff065a5bc1d31f0e5d1bba850d0b3c/src/array.js#L893-L1173
퀵 정렬의 경우 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연산의 횟수 때문에 기본적인 내장 정렬 함수들도 퀵 정렬 기반의 정렬 함수들이 아닐까 생각해본다.
