제 5장: 정렬과 검색(5)

56. 정렬된 여러 개의 데이터 열을 합체시키는 병합(merge)

• 병합(Merge)알고리즘을 활용한 정렬 알고리즘 → 병합 정렬

• 병합 알고리즘이란? 정렬된 여러 개 데이터 열들을 정렬된 하나의 데이터 열로 만드는 알고리즘.

• 예시

  • 데이터 열 A, …, A1, A2, A3, …, Aj
  • 데이터 열 B, …, B1, B2, B3, …, Bk
  • 데이터 열 C, …, C1, C2, C3, …, Cm

  → 위 세개 열을 병합해 하나의 정렬된 데이터 열 P(P1, P2, P3, … Pn)을 생성

  • 이 때 P의 1번째 데이터, 즉 데이터 열 A, B, C 에서의 최소값은 각 데이터열이 오름차 순으로 정렬되어있으므로 반드시 A1, B1, C1중 하나이다.
  • 따라서 P1 = A1, B1, C1의 크고 작음만 따지면 구할 수 있다
  • B1이 최소값이라면 b1을 꺼내 P1에 넣는다.
  • B2 가 데이터 열 B의 첫번째 데이터가 된다
  • P2의 값은 A1, B2, C1 중 하나이다.
  • 데이터가 없어질 때까지 동일하게 반복한다.

57. 병합 알고리즘을 이용해 정렬하는 병합 정렬

• 병합 정렬: 데이터 열의 병합 작업을 이용한 정렬 알고리즘

• 정렬 단계

  1단계: 데이터 열을 2개로 나눈다.

  • 정렬할 데이터 열을 2개로 나눈다. 2개로 나눈 데이터 열을 다시 2개로 나누고, 또 다시 2개로 나눈다. 분할 단계는 나뉜 데이터 열의 요소 개수가 하나가 될 때까지 반복한다.

  2단계: 데이터 열을 병합한다.

  • 분할된 데이터 열들이 하나가 되도록 병합한다.
  • 병합한 데이터 열을 또 다시 병합한다(데이터 열이 하나가 될 때까지 반복)