알고리즘 4강 :: 합병 정렬, 선택 문제

알고리즘 4강을 보며 배운내용

 

 

분할정복 알고리즘 2탄

=> 분할정복 알고리즘 1탄: 이진 탐색, 퀵 정렬

 

복습

• 순환적으로 문제를 하향식 접근으로 푼다
• 분할 - 정복 - 결합으로 문제를 푼다
• 분할된 문제는 크기만 작고 원래 문제와 같다

 

오늘은 합병정렬과 선택문제

 

합병 정렬

분할 정복 방법으로 정렬

분할, 정복, 결합을 잘 지키는 정렬

n만큼 저장장소(왼쪽배열, 오른쪽배열)가 필요하다

 

⌛ 시간 복잡도

O(nlogn)

 

✨ 방법

1. 분할: 동일한 크기로 나누기
2. 정복: 부분배열을 순환적으로 정렬
3. 결합: 합병해서 정렬된 배열 만든다

 

🤖 코드

// 합병 정렬 JavaScript
function mergeSort(원배열, 길이) {
  if(n > 1) {
    let mid = Math.ceil(길이 / 2)
    let 왼쪽배열 = mergeSort(원배열[0 .. mid - 1], mid)
    let 오른쪽배열 = mergeSort(mergeSort[mid .. 길이 - 1], 길이 - mid)
    
    원배열 = merge(왼쪽배열, 오른쪽배열, mid, n - mid)
  }
  return 원배열;
}

// merge JavaScript
function merge(왼쪽배열, 오른쪽배열, n, m) {
  let i, j, k = 0;
  
  // 비교해서 작은값 원배열로 이동
  while(i < n && j < m){
    if(왼쪽배열[i] <= 오른쪽배열[j]) {
      원배열[k++] = 왼쪽배열[i++]
    } else {
      원배열[k++] = 오른쪽배열[j++]
    }
  }
  
  // 남은 왼쪽, 오른쪽 배열 원배월 맨 뒤로 붙이기
  for(i; i<n; i++){
    원배열[k++] = 왼쪽배열[i]
  }
  for(j; j<m; j++) {
    원배열[k++] = 오른쪽배열[j]
  }
  
  return 원배열
}

 

 

선택 문제

배열에서 i번째 작은 원소 찾는 문제

최솟값, 중간값, 최댓값 찾을 수 있다

 

여러 방법들

오름차순 정렬하고 i번째 원소 찾는 방법 => O(nlogn)

최솟값 찾는 i번 반복 => O(n제곱)

 

⌛ 시간복잡도

O(n)

 

✨ 방법

항상 반으로 부분배열이 나눠지도록 피벗 선택

 

피벗 선택 방법(중간값들의 중간값 찾기)

1. 크기 n 배열을 5개씩 묶어서 n/5개 그룹 만든다
2. 마지막에 5개 그룹 안된 원소 그대로 남겨둔다
3. 각 그룹에 중간값 찾고,
4. 중간값 중에서 또 중간값 찾는다 => 피벗

 

pseudo 코드

function selection(원배열, 길이, 찾고 싶은 i번째) {
  if(길이 <= 5) {
    원배열에서 i번째 원소 찾아서 return
  } else {
    원배열 5개씩 묶어서 그룹 생성
    
    각 그룹 중간값 구하고, 이들로 중간값배열 구성
    
    피벗(중간값의 중간값) 계산하려고 선택함수 재귀 호출
    pivot = selection(중간값배열, 그룹갯수, 그룹갯수/2)
    
    피벗 사용해서 원배열 분할
    if( i == j + 1 ) {
      return 원배열
    } else if( i < j + 1 ) {
      selection(원배열[0 .. j - 1], j, i)
    } else {
      selection(원배열[j + 1 .. 길이 - 1], 길이 - j - 1, i - j - 1)
    }
  }
}

 

퀵 정렬의 partition()이용할 수 있는데
시간복잡도 O(n제곱)