[알고리즘] HeapSort보다 QuickSort가 더 빠른 이유

1. 왜 HeapSort보다 QuickSort가 현실적으로 더 빠를까?

HeapSort와 QuickSort는 대표적으로 O(NlogN)안에 동작하는 정렬알고리즘이다.

하지면 현실성면에서 QuickSort가 더 빠르다는것은 익히 들어 알고있을 것 이다.

 

왜 그런것 일까? 

 

이에 대하여 알아보자

 

1-1) 알고리즘의 성능 요인

크게 정렬 알고리즘에서 성능을 미치는 원인은 크게 3가지로 볼 수 있다.

1. 비교 및 스왑을 수행하기 위한 반복자(loop) = 반복자가 어떻게 구현되어있는가의 문제
2. 유효 접근 시간 (지역성)
3. 메모리 소비량

 

1번의 경우 대부분 시간복잡도를 측정할때 고려하는 요소라, O(NlogN)이라는 표기안에 포함되어있는 개념이다.

따라서 HeapSort와 QuickSort의 차이는 2번인 유효 접근 시간(지역성)을 살펴봐야 알 수 있다.

유효 접근 시간(지역성)은 알고리즘의 성능에 크게 영향을 미치는 부분이기 때문이다!

 

1-2) 유효 접근 시간 (지역성)

아주아주 간단하게 말해서 CPU에서 참조하는 주소를 읽어들이는 비용을 말하는데, 지역성을 얼마나 지키는지에 따라서 알고리즘의 성능이 달라진다.

 

Cahce는 CPU 칩 안에 들어가는 매우 빠른 메모리라는 건 아마 대부분 알 것입니다.

이 캐시 메모리가 중요한 이유는 프로세서가 매번 메인 메모리에 접근해 데이터를 받아오면 시간이 오래 걸리기 때문에 캐시(Cache)에 자주 참조되는 데이터를 담아두고, 해당 데이터가 필요할 때 메인 메모리 대신 캐시에 접근하도록해 처리 속도를 높인다.

 

그러면 캐시를 어떻게 효율적으로 관리 하느냐의 문제인데, 결국 캐시에 들어있는 데이터가 얼마나 쓸모있는 데이터가 담겨져 있느냐에 따라 성능이 좌우된다는 것이다. 이를 적중률(Hit-rate)이라고 하는데, 이러한 적중률을 높이기 위한 메커니즘으로는 크게 3가지로 볼 수 있다.

1. 공간 지역성 : 최근에 접근한 데이터의 주변 공간에 다시 접근하는 경향이 강할 수록 적중률이 높음
2. 시간 지역성 : 최근 접근한 데이터에 다시 접근하는 경향이 높을 수록 적중률이 높음
3. 순차 지역성 : 데이터가 순차적으로 접근하려는 경향이 강할 수록 적중률이 높음

이 때 우리는 정렬이 목적이지 않는가? 주로 참조되는 때는 비교 및 swap 과정 일것이다.

이 말은 즉, 결국 같은 비교 및 swap 횟수를 갖고 있더라도 비교하거나 swap하는 이벤트 내에서 얼마나 지역성을 만족하는지(요소들이 근처에서 발생하는지)에 따라 성능이 좌우된다는 것이다.

 

그러면 위에 대한 내용의 연장선상에서 같은 시간 복잡도를 갖는 O(NlogN)의 정렬 알고리즘 중 Heap Sort보다 Quick Sort가 더 빠른지를 설명 할 수 있게됩니다!

 

Heap Sort는 힙 트리 구조를 활용하기 때문에 부모 혹은 자식 노드를 찾기 위해서는 현재 노드의 절반(1/2) 혹은 두 배씩 이동해야한다.

또한 정렬을 위해 하위 트리부터 root tree까지 Heap을 만족하도록 해야하기 때문에 이동하지 않아도 될 불필요한 요소들도 교체될 가능성이 매우 높다.

 

반면에 Quick Sort(middle pivot 기준)의 경우 pivot을 기준으로 양쪽에서 순차적으로 접근하면서 데이터를 비교하기 때문에 지역성이 높을 뿐더러 교환이 불필요한 요소들을 거의 교환하지 않아 swap비용 자체는 높더라도 교환 횟수의 이점 때문에 평균적으로 성능이 뛰어난 것 입니다!