Quick Sort vs Merge Sort TIL

Quick Sort

Quick Sort는 분할 정복 알고리즘의 일종이다. 평균 시간 복잡도는 (O(n \log n))이지만, 최악의 경우 시간 복잡도는 (O(n^2))에 달할 수 있다. 이 정렬 방식은 Pivot을 선택하고, Pivot보다 작은 요소는 Pivot의 왼쪽, 큰 요소는 오른쪽으로 분할하여 정렬을 수행한다. 추가 메모리가 거의 필요 없는 in-place 정렬 방식이며, Pivot 선택 방법에 따라 성능이 크게 달라질 수 있다.

특징

• 분할 정복 방식을 사용한다.
• 평균 시간 복잡도는 (O(n \log n))이며, 최악의 경우 (O(n^2))이다.
• Pivot을 기준으로 배열을 분할하여 정렬한다.
• 추가 메모리 사용이 거의 필요 없는 in-place 정렬이다.
• Pivot의 선택에 따라 성능 차이가 크다.

개선 방법

• Pivot 선택 개선: Pivot을 무작위로 선택하거나, 배열의 첫 번째, 마지막, 중간값 중 중간값(median-of-three)을 Pivot으로 선택함으로써 최악의 성능을 피할 수 있다.
• 3-way partitioning: 동일한 키 값을 가진 요소들을 효율적으로 처리하여 성능을 개선한다.

Merge Sort

Merge Sort 역시 분할 정복 알고리즘의 일종이다. 모든 경우에 대해 시간 복잡도는 (O(n \log n))이며, 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 다음, 두 부분을 병합하는 방식으로 작동한다. 정렬 과정에서 추가 메모리가 필요한 out-of-place 정렬 방식이며, Stable 정렬 방식이다.

특징

• 분할 정복 알고리즘을 사용한다.
• 모든 경우에 대해 시간 복잡도는 (O(n \log n))이다.
• 배열을 반으로 나누고 재귀적으로 정렬한 후 병합한다.
• 추가 메모리가 필요한 out-of-place 정렬이다.
• Stable 정렬 방식이다.

Quick Sort에서 (O(n^2))이 걸리는 예시 및 개선 방법

예시

이미 정렬된 배열에서 최소값이나 최대값을 Pivot으로 선택할 경우, Quick Sort의 성능은 최악의 시간 복잡도인 (O(n^2))에 도달할 수 있다.

개선 방법

• Pivot 선택 개선: Pivot 선택을 개선하기 위해 배열의 첫 번째, 마지막, 중간값 중 중간값을 Pivot으로 선택하는 median-of-three 방식을 사용할 수 있다. 또한, Pivot을 무작위로 선택하는 방법도 성능을 개선하는 데 도움이 될 수 있다.
• 3-way partitioning: Pivot과 동일한 값을 가진 요소들을 효율적으로 처리하기 위해 3-way partitioning을 사용함으로써, 동일한 값들이 많은 배열에서의 성능 저하를 방지할 수 있다.