240202 동계 모각코 5차

병합 정렬 

정렬된 두 배열이 있다고 가정했을 때, 두 배열을 합쳐 하나의 정렬된 배열로 만드는 방법은 두 개의 배열 처음부터 시작하여 두개의 값 중 더 작은 값을 배열에 넣고, 다시 남은 값을 비교하는 방식으로 채워나가는 것이다. 두 배열의 원소를 N개라고 가정한다면, 각 원소는 단 한번만 이동을 하게 되므로 시간복잡도는 O(N) 이 된다. 

그러나 우리가 정렬해야되는 배열은 한개다. 따라서 배열을 두개로 쪼개준다. 언제까지 ? 배열의 원소개 1개가 될 때 까지 재귀적으로 쪼개준다. 쪼갠 후 정렬을 하고, 다시 합치므로 이러한 방식을 divide and conquer 이라고 부른다. 

병합정렬의 시간 복잡도는 O(nlogn) 이다. 쪼개는데에 logn, 배열을 이동하는 데에 n 만큼의 시간이 소요되기 때문이다. 

 

function merge_sort(arr[], low, high)
  if low < high
    set mid = (low + high) / 2
    merge_sort(arr, low, mid)
    merge_sort(arr, mid+1, high)
    merge(arr, low, mid, high)


set merged_arr = []

function merge(arr[], low, mid, high)
  set i = low, j = mid + 1

  set k = low
  while i <= mid && j <= high
    if arr[i] <= arr[j]
      merged_arr[k] = arr[i]
      k += 1; i += 1
    else
      merged_arr[k] = arr[j]
      k += 1; j += 1
  
  while i <= mid
    merged_arr[k] = arr[i]
    k += 1; i += 1

  while j <= high
    merged_arr[k] = arr[j]
    k += 1; j += 1
  
  for k = low ... k <= high
    arr[k] = merged_arr[k]
  
  return arr 

 

파이썬 코드는 다음과 같다. 먼저 원소의 개수가 2개 이상인 경우, 리스트를 반으로 갈라 좌,우 측에 대한 정렬을 재귀적으로 수행한다. 

 

function merge_sort(arr[], low, high)
  if low < high                  // 원소의 개수가 2개 이상인 경우에만 진행
    set mid = (low + high) / 2   // 가운데 원소의 위치
    merge_sort(arr, low, mid)    // 왼쪽 부분에 대해 병합정렬 진행
    merge_sort(arr, mid+1, high) // 우측 부분에 대해 병합정렬 진행
    merge(arr, low, mid, high)   // 정렬된 두 리스트를 하나로 병합

 

이제 정렬된 다음 두 구간 내의 리스트에 대해 합치는 작업을 진행하는데, 두 리스트 ( i, j ) 를 비교하여 더 작은 원소를 합쳐진 배열에 넣어준다. 

 

set merged_arr = []           // 병합 이후의 결과를 담아줍니다.

function merge(arr[], low, mid, high)
  set i = low, j = mid + 1      // 각 리스트 내의 원소 위치를 잡습니다.

  set k = low                   // 병합 시 원소를 담을 위치를 유지합니다.
  while i <= mid && j <= high   // 두 리스트 내의 원소가 아직 남아있다면
    if arr[i] <= arr[j]          // 첫 번째 리스트 내의 원소가 더 작다면
      merged_arr[k] = arr[i]    // 해당 원소를 옮겨줍니다. 
      k += 1; i += 1
    else
      merged_arr[k] = arr[j]    // 그렇지 않다면 두 번째 리스트 내의
      k += 1; j += 1            // 원소를 옮겨줍니다.
  
  while i <= mid                // 아직 첫 번째 리스트 내 원소가 남아있다면
    merged_arr[k] = arr[i]      // 남은 원소들을 전부 옮겨줍니다.
    k += 1; i += 1

  while j <= high               // 아직 두 번째 리스트 내 원소가 남아있다면
    merged_arr[k] = arr[j]      // 남은 원소들을 전부 옮겨줍니다.
    k += 1; j += 1
  
  for k = low ... k <= high     // 병합된 리스트를 다시
    arr[k] = merged_arr[k]      // 원본 리스트에 옮겨줍니다.
  
  return arr 

 

바로 직전학기 알고리즘 수업때 중요하게 다루어졌던 부분이다. 아직도 코드가 수월하게 이해되지는 않지만, 계속 보다보니 어느정도 알 것 같다. 

 

function merge_sort(arr[], low, high)
  if low < high
    set mid = (low + high) / 2
    merge_sort(arr, low, mid)
    merge_sort(arr, mid+1, high)
    merge(arr, low, mid, high)


set merged_arr = []

function merge(arr[], low, mid, high)
  set i = low, j = mid + 1

  set k = low
  while i <= mid && j <= high
    if arr[i] <= arr[j]
      merged_arr[k] = arr[i]
      k += 1; i += 1
    else
      merged_arr[k] = arr[j]
      k += 1; j += 1
  
  while i <= mid
    merged_arr[k] = arr[i]
    k += 1; i += 1

  while j <= high
    merged_arr[k] = arr[j]
    k += 1; j += 1
  
  for k = low ... k <= high
    arr[k] = merged_arr[k]
  
  return arr 

 

문제로 위의 코드에서 arr = [ 17, 21, 15, 16, 30, 20, 35 ] 일때, 함수가 7번 종류된 시점에서의 배열의 상태를 물어봤다. 

이때 진행과정은 다음과 같다. 

 

 

 

그 다음은 2,3 -> 2,2 -> 2,2 -> 3,3 -> 3,3 -> 2,3 ---> 0,3 

 

7번 종류되었을 때 arr는 0,3 구간이 정렬된 상태이므로 , 

15 16 17 21 30 20 35 가 정답이 된다. 쉽지 않은 문제였다.