Quick Sort 더 알아보기 - 2
Implements
C / C++을 기준으로 기본 라이브러리로 되어있는 Quick Sort에 대해 이야기를 해보겠다
C에 있는 qsort 함수는 Quick Sort 알고리즘으로 구현이 되어있다
C++의 경우에는 기본이 Quick Sort이나 Merge Sort와 같은 다양한 정렬을 지원한다
Complexity
qsort의 경우에는 복잡성을 고려하지 않는다
sort의 경우에는 C++11을 기준으로 Worst Case에서 O(n logn)을 요구한다
Modern C++(C++20이 나온 시점에서 C++11을 모던이라하는것도 이상하다) 이전의 경우에는 O(n^2)까지 허용했다
Performance
qsort 와 sort에 대해서 실험한 결과 sort가 더 우수한 퍼포먼스를 보였다
Stability
qsort의 경우에는 void* 로 접근하기 때문에 sort의 경우가 safety하다
또한 sort는 배열, STL, class 등 다양한 컨테이너에서 지원이 가능하기 때문에 활용도가 높다