4강 분할정복 알고리즘(2)

합병정렬

• 주어진 배열을 정렬하는 전형적인 분할정복 방법이 적용된 알고리즘이다. 같은 크기의 두 부분배열로 분할하고 순환 호출하여 정렬하는 방식
  1. 분할: 배열을 동일한 크기의 두 개의 부분배열로 분할
  2. 정복: 각각의 부분배열을 순환적으로 정렬
  3. 결합: 정렬된 부분배열을 합병하여 하나의 정렬된 배열로 만든다
• 합병 함수 수행시간
  O(n)
• 합병 정렬 함수의 수행시간
  T(n) = O(nlogn)
• 입력 크기 n 만큼의 추가적인 저장 장소가 필요하다

선택문제

• n개의 원소가 임의의 순서로 저장된 배열 A[0..n-1] 에서 i번째로 작은 원소를 찾는 알고리즘이다.
  i = 1 → 최소값, i = n/2 → 중간값, i = n → 최댓값
• 시간복잡도
  최악의경우: O(n**2), 평균: O(n)
• 방법
  1. 퀵 정렬의 분할 함수를 순환적으로 적용하는 방법
     1. 분할: 피벗을 기준으로 주어진 배열을 분할하고 i가 피벗의 인덱스와 같으면 반환
     2. 정복: i가 피벗보다 작으면 왼쪽부분, 크면 오른쪽부분을 반복해준다 - 성능
        퀵 정렬을 사용하는 알고리즘이기 때문에 퀵 정렬의 성능을 따라간다.
        최악의 경우 → O(n**2)
        평균적인 경우 → O(n)
        → 항상 일정한 비율의 두 부분배열로 분할하면 성능이 개선된다
  2. 항상 일정한 비율의 두 부분배열로 분할되도록 특정 성질을 만족하는 값을 피벗으로 선택한다.
     • 피벗 선택방법
  3. 크기가 n인 배열의 원소를 5개씩 묶어서 그룹으로 만듬
  4. 각 그룹에 대해 중간값을 찾음
  5. 각 그룹의 중간값 중 다시 중간 값을 찾음 → 피벗
     • 성능
       최악의 경우 → O(n)
       평균적인 경우 → O(n)