이 글을 쓰게 된 계기
2020년 여름 K 기업에 인턴십 면접을 보는 과정에서, 왜 Quick Sort가 다른 Sorting 알고리즘들 보다 더 자주 사용되는지(더 빠른지?)에 대한 질문을 받았었습니다. 그 때 저의 대답은 "캐싱하는 측면에서 이점이 있다?"라는 식으로 답변을 했던 것 같습니다. 하지만, 구체적으로 이를 설명해내지는 못했습니다. 의도했는지는 모르겠지만, 면접관분들의 반응은 캐싱 개념과는 관련이 없는데?의 반응이었습니다. 다양한 Sorting 알고리즘과 비교해가며, Quick Sort가 자주 사용되는 지 설명할 수 있었으면 좋겠으면 해서 정리해 보고자 합니다.
추가적으로 학교 수업 시간에 왜 O(nlogn)의 Sorting algorithm이 많은데 QuickSort를 사용하는 지에 대한 질문이 있었고, 이를 함께 정리하고자 한다.
Quick Sort
Quick Sort작동 로직을 간단한게 정리하면 다음과 같다.
1. pivot을 선택한다.
pivot을 선택하는 방법 또한 다양하게 할 수 있다. 애니메이션에서는 계속 오른쪽의 값을 pivot값으로 정해두고 사용하였다. -> 이때 이미 정렬되어져있는 경우에는 모든 경우 모든 피봇에 대하여 swap을 진행해야한다. O(n^2)
이를 해결하기 위한 방법: 랜덤한 피봇을 선택하는 방법. Median Of Three Pivot의 방법도 있다고 한다.
(이 문제에 관해서도 면접에 등장했는데, 어떤 형태에 데이터 셋인지 정해지지 않은 랜덤 셋에 대하여, 가장 오른쪽 값을 정하는 경우나, 랜덤한 값을 고르는 경우나 마찬가지의 경우가 아닌가라는 역질문을 던졌는데, 지금까지도 정답을 모르겠다.) -> 이 생각을 하게 된 배경은, 랜덤 셋이기 때문에, 가장 오른쪽 값을 정했을때나, 랜덤한 값을 고르는 경우나, 정렬되어진 순서로 값을 고르는 확률은 동일하다고 생각한다.
물론, 정렬되어져있다는 전제가 되어있는 경우에는 랜덤한 값을 고르는게 당연히 더 빠른 sorting 알고리즘이 될것이다.
-
Swap
구현에 따라 다를 수 있겠지만, in-place로 구현이 진행된다.
왼쪽 끝,오른쪽 끝에 포인터가 하나씩 있으며, 왼쪽 포인터는 피봇보다 작은 경우 계속 오른쪽으로 이동, 오른쪽 포인터는 피봇보다 큰 경우 계속 왼쪽으로 이동. 왼쪽 포인터가 피봇보다 큰 값을 만나고, 오른쪽 포잍너가 피봇보다 작은 값을 만나면 그 둘의 값을 swap을 진행한다. 두 포인터가 만났을때, 그 값을 피봇과 swap한다. -
pivot값을 나누어진 좌우에서 1,2 번의 과정을 계속 진행해 나간다.
Quick Sort vs Merge Sort
Quick Sort와 Merge Sort의 차이를 잘 설명되어 있어 글의 일부를 간단히 번역해 봤습니다.
https://stackoverflow.com/questions/29218440/when-merge-sort-is-preferred-over-quick-sort
왜 Quick Sort가 Merge Sort보다 대체로 빠른 이유를 알면, 어떤 상황에서 Merge Sort를 사용하는지 알 수 있을겁니다. 다음의 2가지 이유가 있습니다.
-
Quicksort는 Mergesort보다 더 좋은 Locality를 가지며, 이는 Access하는 성능에서 Quick Sort가 대게 빠른 것을 의미한다.(Array로 구현된 Mergesort는 merging과정에서 합치는데 사용되는 새로운 Array가 필요합니다)
-
Quicksort는 잘 구현하면, 최악의 경우 O(log n)의 메모리를 사용하는 반면, Mergesort는 merging의 오버헤드 떄문에 O(n)의 메모리를 필요로한다.
(참고로 우리 수업때 구현한 Quicksort의 메모리는 worst case 일때 O(n)을 사용합니다. 조금 수정된 Quick sort를 사용하면 O(log n)으로 줄일 수 있다고 합니다.
궁금하신분을 아래 영상을 참고해주세요
이 장점들이 사라지는 하나의 시나리오가 있습니다. 우리가 이전에 배웠던 Linked LIst를 sorting한다고 가정해보세요. Linked List는 메모리상 분산되어 있을것이며, 이는 1번 장점이 사라집니다. 또한 Linked list는 merge하는데 O(1)의 공간만 사용되기 때문에 O(n)의 space Overhead를 줄일수 있으므로 (2)번 장점이 사라집니다. (아마 포인터의 위치만을 변경해주기에 추가적인 공간은 사용되지 않는 것으로 보입니다.
결과적으로 Linked list를 sorting 하는데 많은 곳에 Merge Sort를 사용되어진다고 하네요.
추가적으로 Merge Sort는 Stable하며, multi-threading에서의 장점도 있다고 하네요.
QuickSort vs HeapSort
둘다 inplace swap을 통해 sorting이 되지만, 데어터 양이 방대해 졌을 때, heapsort는 child node와의 거리가 멀어지는 반면에, quicksort는 연속적으로 위치해 있어, 조금 더 Locality를 활용하는 측면에서 빠르다고 하네요! 아래 링크의 글을 참고했습니다. 읽어보셔도 좋을거 같아요
https://stackoverflow.com/questions/2467751/quicksort-vs-heapsort
Heap Sort is a safe bet when dealing with very large inputs. Asymptotic analysis reveals order of growth of Heapsort in the worst case is Big-O(n logn), which is better than Quicksort's Big-O(n^2) as a worst case. However, Heapsort is somewhat slower in practice on most machines than a well-implemented quick sort. Heapsort is also not a stable sorting algorithm.
The reason heapsort is slower in practice than quicksort is due to the better locality of reference ("https://en.wikipedia.org/wiki/Locality_of_reference") in quicksort, where data elements are within relatively close storage locations. Systems that exhibit strong locality of reference are great candidates for performance optimization. Heap sort, however, deals with larger leaps. This makes quicksort more favorable for smaller inputs.
