Quick sort, Merge sort는 이전 게시물인 https://nueahx7674.tistory.com/6 에서 확인 할 수 있다.
해당 게시글에서는 Quick Sort와 Merge sort의 차이를 중점적으로 다룬다.
Quick Sort와 Merge Sort의 차이
- 퀵소트는 불안정 정렬, 병합 정렬은 안정 정렬이다.
- 퀵 정렬은 최악의 경우(오름차순 정렬이거나 내림차순 정렬일 경우) O(n^2)의 시간 복잡도를 가지지만 병합 정렬은 O(n log n)으로 동일하다.
- 병합 정렬은 추가 메모리 공간을 필요로 한다.
- 퀵 정렬이 평균 시간 복잡도에서는 Merge Sort보다 빠르다. 이는 아래에서 자세히 설명하겠다.
Quick Sort가 Merge Sort보다 빠른 이유
이를 설명하기 위해서는 지역성의 개념이 필요하다.
지역성(Locality)은 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향을 말한다.
어떠한 작업을 수행할 때 자주 사용하는 코드와 데이터를 캐시에 올린다면 아주 빠른 성능을 얻을 수 있게 된다.
캐쉬에 없는 다른 페이지로 이동하면 page cache hit 비율이 떨어지게 되고, 결국 physical memory로 접근을 해야 하기 때문에 시간이 상대적으로 오래 걸린다.
Merge Sort가 진행되는 방식을 애니메이션으로 표현한 그림은 다음과 같다.
애니메이션 효과를 보면, 계속해서 처음과 끝을 왔다 갔다하면서 데이터를 탐색한다. 한 개의 사각형들이 한 개의 페이지라면, 캐쉬의 페이지가 계속해서 바뀌기 때문에 locality의 효과가 떨어지게 된다.
Quick Sort가 진행되는 방식을 애니메이션으로 표현한 그림은 다음과 같다.
처음에 전체 탐색을 하면서 pivot을 기준으로 좌우로 나눈다. 그 후, 좌우로 나눠서 재귀적으로 pivot을 기준으로 좌우를 나눈다. 해당 과정을 반복하면 정렬이 끝난다.
퀵 정렬은 나눈 부분 각각에 대해 정렬을 진행하기 때문에 상대적으로 한정적인 범위에서 데이터들이 움직인다. 그래서 병합정렬에 비해 자주 캐시에 있는 페이지들을 바꿀 필요가 없다.
결론적으로 퀵정렬은 병합정렬보다 더 참조의 지역성의 성질을 띠기 때문에 캐쉬의 도움을 더욱 받을 수 있게 된다. 그래서 일반적인 상황에서는 퀵정렬이 더 빠르다.
참고 자료
'Computer Science > 알고리즘, 자료구조' 카테고리의 다른 글
| 그래프와 탐색 (0) | 2023.04.01 |
|---|---|
| 시간 복잡도 (0) | 2023.03.31 |
| 자료구조 - Tree, Binary Tree (0) | 2023.03.31 |
| 자료구조 - 선형 자료구조 (0) | 2023.03.31 |
| 정렬 알고리즘 (0) | 2023.01.31 |
