[Study Log] 병합 정렬 vs 퀵 정렬

- 배운 주제

• 순열
• 그리디
• 분할 정복
• AI 오케스트레이션

- 핵심 개념 키워드

• 순열
• 그리디
• 이진 검색
• 병합 정렬 & 퀵 정렬

- 이해한 포인트

순열

서로 다른 원소들을 특정한 순서로 나열하는 것

$nPr = n * (n-1) * (N-2) * ... * (n-r+1)$

순열을 구현하는 방식이 다양하다는 것을 알게 되었다.
기존에는 반복문 또는 방문 체크를 통해 구현했었는데, swap과 비트마스킹 방식도 있다는 것을 알게 되었다.

분할 정복

큰 문제를 작은 하위 문제로 나누어 해결하는 방식

설계 전략
분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다
정복 (Conquer) : 나눈 작은 문제를 각각 해결한다
결합 (Combine) : (필요하다면) 해결된 해답을 모은다

병합 정렬 vs 퀵 정렬

병합 정렬 과정

병합 정렬의 시간 복잡도는 $O(N log N)$으로 고정이고 안정 정렬이다. 대신 $O(N)$의 추가 메모리가 필요하다.
퀵 정렬은 평균 $O(N log N)$이고 최악은 $O(N^2)$이다. 그리고 안정 정렬이 보장되지 않는다. 하지만 추가 메모리는 $O(1)$만 요구된다.

따라서 메모리를 아껴야 하는 상황에서는 퀵 정렬이 유리하고, 안정 정렬이나 $O(N log N)$ 보장이 필요한 상황에서는 병합 정렬이 좋을 거 같다.

병합 정렬 & 퀵 정렬 비교표

정렬	시간 복잡도	메모리	안정성
병합 정렬	$O(N log N)$	O(N)	안정 정렬
퀵 정렬	평균 $O(N log N)$	O(1)	안정 정렬 x