알고리즘 3줄 정리 [합병정렬, 퀵정렬]

Divid and Conquer 의 형제

• 합병정렬 정리
  1. 핵심개념: 리스트를 반으로 나누고, 각 부분을 재귀적으로 정렬한 다음, 두 부분을 합병합니다.
  2. 시간복잡도: 최선, 평균, 최악 모두 O(nlogn) → + : 일관된 시간복잡도
  3. 공간복잡도: O(n) (추가 배열을 사용하기 때문에) → - : 추가 메모리 필요
• 퀵정렬 정리
  1. 핵심개념: 피벗을 선택하여 이보다 작은 요소와 큰 요소를 분할한 후(파티션), 각 부분을 재귀적으로 정렬합니다.
  2. 시간복잡도: 평균 O(nlogn), 최악 O(n2) (피벗 선택에 따라 달라짐) → + 평균적으로 빠름, 최악 크게 증가
  3. 공간복잡도: 평균 O(logn) (재귀의 깊이), 최악의 경우 O(n) (피벗 선택이 최악일 때) → + 추가 메모리 적게 소모
  4. 이름이 퀵정렬인 이유 : 다른 비교 기반 정렬 알고리즘들에 비해 일반적으로 더 빠르게 작동한다는 사실에서 유래 (1960년대 기준)