[Data Structure] 퀵 정렬 - Quick Sort

퀵 정렬 (Quick Sort) Unstable Sort 분할 정복(Divide and Conquer) 알고리즘 다른 원소들과의 비교만으로 정렬 수행 Merge Sort와 다르게, Quick Sort는 비균등하게 분할 평균적으로 매우 빠른 수행 속도 > C에서는 라이브러리 함수로 qsort가 주어진다 > Java의 Arrays.sort는 quick sort로 구현되어있다 시간복잡도 - 최선/평균 : O(n log n) - 최악 : O(n²) 장점 - 속도가 빠르다 - O(n log n)을 가지는 다른 정렬 알고리즘과 비교해도 가장 빠르다 - 추가 메모리 공간이 필요없다 단점 - 정렬된 리스트에 대해 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다 pivot을 선택할 때 리스트를..

2022.01.03