Quick Sort 더 알아보기 - 1
대표적으로 O(nlog n)의 시간복잡도를 가지는 알고리즘은 머지 소트, 힙 소트, 퀵 소트가 있다
이중 퀵 소트가 보편적으로 가장 빠르다고 평가된다 Worst Case의 경우를 제외하고 이야기를 하더라도 모두 O(nlog n)인데 어느 근거로 퀵 소트가 가장 빠른지 이야기를 해보자
보편적으로 말하는 Big-O Notation에서 O(n logn)이라 함은 C * n * logn + a 을 이야기한다
여기서 a값은 대체로 무시되는 값이며 n * logn의 성능을 결정하는 척도는 C값이 결정한다
이 C값에서 가장 큰 영향을 미치는 것은 Cache Locality가 해당이 된다
Heap Sort의 경우는 배열로 구현을 하게 된다면 다음 비교를 위해 Index * 2 와 Index * 2 + 1의 데이터가 존재하는 메모리 주소로 접근을 해야한다 이는 Cache Locality를 제대로 활용하기 힘든 접근이다
Merge Sort의 경우는 처음부터 분할을 시작해 접근하는 메모리 주소 영역의 범위가 작아졌다가 합병을 하는 과정에서 전체 데이터에 접근을 하게 된다 이 또한 Cache Locality를 잘 반영하기 어렵다고 이야기할 수 있다
Quick Sort의 경우는 처음 하나의 Pivot을 선정후 해당 피벗을 기준으로 나머지 엔티티들을 이동시키고 이 과정을 반복적으로 수행한다 정렬을 지속적으로 수행할 수록 Memory Access는 최근에 Access했던 장소에 접근이 되게된다 그렇기 때문에 Quick Sort가 O(n logn)의 시간을 가지는 정렬중 가장 빠르다고 평가가 된다 하지만 최악의 피벗 선정이 반복되면 O(N^2)의 시간 복잡도가 수행되는 것은 사실이다