정렬 정리 - 퀵, 머지

퀵 정렬

• pivot을 이용한 divide and conquer
• 평균 시간 복잡도 O(NlogN)
  • 탐색의 깊이 : N = 2^k → k번 순환 호출 한다 → k = logN
  • 각 단계에서 비교 : N
• 최악 시간 복잡도 O(N^2)
  • 탐색의 깊이 : N
  • 각 단계에서 비교 : N
  • 이미 정렬된 대상을 다시 퀵 정렬하는 경우 분할이 불균형하게 이루어져 최악의 시간 복잡도를 가지게 된다.
• 다른 O(NlogN) 정렬과 비교해봐도 속도는 가장 빠르다.
• 추가 메모리 공간이 필요로 하지 않는다.
• 퀵 정렬 참고

퀵 정렬 과정

(1) 피벗 설정
(2) 피벗보다 작은 것은 왼쪽, 큰 것은 오른쪽
(3) 각각의 범위에서 재귀적으로 (1)단계 다시 수행

머지 정렬

• divide and conquer
• 정렬 대상을 분할한다. → 분할 된 것들을 합치며 정렬한다.
• 평균 시간 복잡도 O(NlogN)
  • 탐색의 깊이 : N = 2^k → k번 순환 호출 한다 → k = logN
  • 각 단계에서 비교 : N
• 어떠한 데이터든 O(NlogN)을 보장한다.
• 정렬을 위한 추가 메모리가 필요하다.
• 머지 정렬 참고

머지 정렬 과정

(1) 데이터를 중앙 기준으로 반으로 나눈다. → 범위가 1이 될 때까지 재귀적으로 반복한다.
(2) 각각 나누어진 범위를 합치며 정렬한다.

많은 상용 라이브러리에서 내부적으로 퀵 정렬을 채택한 이유?

• 퀵 정렬은 추가적인 메모리 공간을 필요로 하지 않는다.
• 퀵 정렬은 초반을 제외하고 넓은 범위에서 움직이지 않아 캐시 HIT가 더 잘 일어난다.(더 좋은 캐시 지역성)

정렬 캐시 지역성 참고