병합정렬(merge sort)

- 재귀용법을 활용한 정렬 알고리즘

1) 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

2) 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬한다.

3) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

=================================

index  :  0     1      2     3    4    5     6    7 

value  : 49   97   53    5   33  65  62  51

=================================

pivot선택 : (index : 0, value : 49)

p1 (1회)

[left]   - (index : 0, value : 49), (index : 1, value : 97), (index : 2, value : 53), (index : 3, value : 5)

[right] - (index : 4, value : 33), (index : 5, value : 65), (index : 6, value : 62), (index : 7, value : 51) 

.  .  . (이런식으로 데이터 수가 1개가 될 때까지...재귀함수 => 분할) 

(index : 0, value : 49), (index : 1, value : 97), (index : 2, value : 53), (index : 3, value : 5), (index : 4, value : 33), (index : 5, value : 65), (index : 6, value : 62), (index : 7, value : 51)

분할과정이 끝나면 합치기(정복-merge)

[1] (index : 0, value : 49), (index : 1, value : 97) // (index : 3, value : 5), (index : 2, value : 53) 

[2] (index : 4, value : 33), (index : 5, value : 65) // (index : 7, value : 51), (index : 6, value : 62)

 

[1] (index : 3, value : 5), (index : 0, value : 49), (index : 2, value : 53), (index : 1, value : 97) //

(index : 4, value : 33), (index : 7, value : 51), (index : 6, value : 62), (index : 5, value : 65)

 

[최종]

(index : 3, value : 5), (index : 4, value : 33), (index : 0, value : 49), (index : 7, value : 51), (index : 2, value : 53), (index : 6, value : 62), (index : 5, value : 65), (index : 1, value : 97)

 

[원리 시각화]

https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/

Merge Sort visualize | Sorting | Algorithms | HackerEarth

 

#코드

import random
 
def mergeSplit(data):
  if len(data) <= 1:
    return data
  medium = int(len(data)/2)
  left   = mergeSplit(data[:medium])
  right  = mergeSplit(data[medium:])
  return merge(left, right)
 
def merge(left, right):
  merged = list()
  left_point, right_point = 0, 0
 
  # CASE_1 : left/right 둘 다 있을 때
  while len(left) > left_point and len(right) > right_point:
    if left[left_point] > right[right_point]:
      merged.append(right[right_point])
      right_point += 1
    else:
      merged.append(left[left_point])
      left_point += 1
  # CASE_2 : left만 남아 있을 때
  while len(left) > left_point:
    merged.append(left[left_point])
    left_point += 1
  # CASE_3 : right만 남아 있을 때
  while len(right) > right_point:
    merged.append(right[right_point])
    right_point += 1
  return merged
 
data_list = random.sample(range(100), 10)
print(data_list)
data_list = mergeSplit(data_list)
print(data_list)
 
 

// 자바 코드

import java.util.*;
import java.io.*;
/*
8
5 7 8 4 9 3 1 2
*/
public class Main{
  
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static int n;
  static int[] numbers = new int[100];
  public static void main(String[] args) throws Exception {
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++) {
      numbers[i] = Integer.parseInt(st.nextToken());
    }
    
    // numbers를 0부터 n-1까지 정렬을 시켜라.
    mergeSort(0, n-1);
    
    for(int i=0; i<n; i++) {
      bw.write(String.valueOf(numbers[i]) + " ");
    }
    
    br.close();
    bw.flush();
    bw.close(); 
  }
  
  
  // numbers의 start부터 end까지를 합병정렬하는 함수.
  static void mergeSort(int start, int end) {
    
    if(start>=end) {
      return;
    } else {
      //1.왼쪽 절반을 합병정렬
      //2.오른쪽 절반을 합병정렬
      //3.합친다.
      int mid = (start + end) / 2;
      mergeSort(start, mid);
      mergeSort(mid+1, end);
      
      // numbers[start ~ mid], numbers[mid + 1 ~ end]는 정렬이 이미 되어있음
      // 왼쪽, 오른쪽을 하나로 합치는 메서드
      merging(start, mid, mid+1, end);
    }
    
  }
  
  static void merging(int s1, int e1, int s2, int e2) {
    // s1 ~ e2 : 이 둘을 합쳐서 정렬된 결과를 만드는 함수.
    int p, q; // p와 q의 현재 최솟값을 가르키는 변수들
    int[] temp = new int[100]; // 합쳐진 결과를 저장하는 임시변수
    int temp_idx = 0; 
    
    p = s1;
    q = s2;
    
    while(p<=e1 && q<=e2) {
      if(numbers[p]<=numbers[q]) {
        temp[temp_idx++] = numbers[p];
        p++;
      } else {
        temp[temp_idx++] = numbers[q];
        q++;
      }
    }
    
    if(p>e1) { // p가 나갔다, q에 원소가 남았다.
      for(int i=q; i<=e2; i++) {
        temp[temp_idx++] = numbers[i];
      }
    } else {
      for(int i=p; i<=e1; i++) {
        temp[temp_idx++] = numbers[i];
      }
    }
    
    // temp는 완성이 되었으니
    // numbers[s1 ~ e2]까지 temp의 값을 복사
    for(int i=s1; i<=e2; i++) {
      numbers[i] = temp[i-s1];
    } 
    
  }  
   
   
}