[Algorithm] 정렬 ②

- 분할정복법 : 분할, 정복, 합병을 거치는 방법

분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

정복 : 각각의 문제를 순환적으로 해결

합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

 

- Merge Sort : 합병정렬

1. 분할 -> 데이터가 저장된 배열을 절반으로 나눔. (divide)

2. 정렬 -> 각각을 순환적으로 정렬함. (recursively sort)

3. 합병 -> 정렬된 두 개의 배열을 합쳐 전체를 정렬함. (merge)

=> 합병 과정이 실질적으로 중요함.

 

Ex) A | G | L | O | R 과 H | I | M | S | T 의 정렬된 두 배열이 있을 때,

A와 H는 각 배열에서 가장 작은 값이며 두 배열을 하나의 배열로 합병할 때 A와 H 둘 중 하나가 가장 작은 값이 됨.

A가 더 작으므로 최종적으로 A가 앞으로 옴.

G와 H 중에서 G가 더 작으므로 G가 앞으로 옴.

H와 L 중에서 H가 더 작으므로 H가 앞으로 옴.

이를 반복함.

앞 배열에서 값이 다 사용되었다면 뒷 배열에서의 남은 값은 그대로 합병되면 됨.(이미 크기대로 배열되어 있기 때문에)

최종적으로 A | G | H | I | L | M | O | R | S | T 이라는 정렬된 리스트를 완성.

 

mergeSort ( A [ ] , p , r ) => A [ p . . . r ]을 정렬함

{ 

     if ( p < r ) then {

        q <- ( p + q ) / 2 ; => p , r의 중간 지점 계산

        mergeSort ( A , p , q ) ; => 전반부 정렬

        mergeSort ( A , q + 1 , r ) ; => 후반부 정렬

        mergeSort ( A , p , q , r ) ; => 합병

     } 

}     

 

merge ( A [ ] , p , q , r )

{ 정렬되어 있는 두 배열 A [ p . . . r ]와 A [ q+1 . . . r ]을 합하여 정렬된 하나의 배열 A [ p . . . r ]을 만든다.  }