[알고리즘] 합병 정렬 merge sort
[알고리즘] 퀵 정렬 quick sort

분할 정복 전략

분할 정복 (divide and conquer) 전력이란?

• 주어진 문제를 (1) 부분 문제들로 분할하고 (2) 각 부분 문제에 대한 해결책을 찾은 후 (3) 부분 해들을 통합하여 원래 문제의 해결책을 찾는 전략

• 분할 정복 전략에 의해 설계된 알고리즘을 분할 정복 알고리즘이라고 한다.

  • 분할 divide: 주어진 문제를 동일한 부분 문제들로 (재귀적으로) 분할하고
    

  • 정복 conquer: 부분 문제들의 부분 해를 찾은 후

  • 통합 combine: (필요 시) 부분 해들을 통합하는 하향식(top-down) 문제 해결 전략'

분할 정복 알고리즘 분류

1. 문제가 각 재귀마다 (1) 두 개의 부분 문제로 분할되고 (2) 부분 문제의 크기가 1/2로 감소하는 알고리즘 (합병 정렬 알고리즘)

2. 문제가 각 재귀마다 (1) 두 개의 부분 문제로 분할되고 (2) 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘 (퀵 정렬 알고리즘)

3. 문제가 각 재귀마다 (2) 두 개의 부분 문제로 분할되고 (2) 그 중 한 개의 부분 문제는 고려할 필요가 없으며, (3) 부분 문제의 크기가 1/2로 감소하는 알고리즘 (이진 검색 알고리즘)

4. 문제가 각 재귀마다 (1) 두 개의 부분 문제로 분할되고 (2) 그 중 한 개의 부분 문제를 고려할 필요가 없으며, (3) 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘 (선택 문제 알고리즘)

정렬

• 탐색과 함께 컴퓨터가 가장 많이 수행하는 연산 중 하나.
• 순서 없이 나열된 항목들을 키값을 기준으로 오름차순 혹은 내림차순으로 재배열시키는 연산.
• 정렬은 탐색 성능을 향상시키기 위해서도 필수적이다.

정렬 알고리즘 분류

내부 정렬

정렬할 항목들의 집합 D가 주기억장치(메인 메모리)에 상주할 수 있을 경우, D를 주기억장치에서 정렬

• 선택 정렬: 평균 수행 시간 O(N**2)
• 삽입 정렬: 평균 수행 시간 O(N**2)
• 셸 정렬: 정확한 수행 시간 분석 어려움
• 힙 정렬: 평균 수행 시간 O(N logN)
• 합병 정렬: 평균 수행 시간 O(N logN)
• 퀵 정렬: 평균 수행 시간 O(N logN)

외부 정렬

정렬하고자 하는 항목들의 집합 D의 사이즈가 커서 보조기억장치(디스크)에 저장하고 이를 작은 크기의 부분 집합 D1, D2,..., Dn으로 나누어 주기억장치에서 정렬하고 합병.