[자바 Do It! 알고리즘]Chapter06 정렬 (병합 정렬)

언젠가 이해되는 날이 오겟죠..

​

병합정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘입니다.

​

[정렬을 마친 배열의 정합]

1. 각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬을

마치는 배열을 만듭니다.

1) 배열 a에서 선택한 요소(a[pa])와 배열 b에서 선택한 요소 (b[pb])를 비교하여 작은 값을 c[pc]에 저장합니다.

그런 다음 커서 pb,pc를 한 칸 옮기고 커서 pa는 그대로 둡니다. 커서 pa,pb가 가리키는 값을 비교하여 작은 값을

c[pc]에 대입하고 커서 pa,pbpc를 진행하는 작업을 반복합니다. 커서 pa가 배열 a의 끝에 다다르거나

커서 pb가 배열 b의 끝에 다다르면 이 작업을 종료합니다.

2) while 문의 실행 조건은 1)의 과정을 통해 배열 b의 모든 요소를 배열 c로 복사하고 배열 a에는 아직 복사하지

못한 요소가 남아 있는 상태를 전제로 합니다. 커서 pa를 한 칸씩 진행하면서 복사하지 않는 모든 배열 a의 요소를

배열 c에 복사합니다.

3) while 문의 실행 조건은 1)의 과정을 통해 배열 a의 모든 요소를 배열 c로 복사하고 배열 b에는 아직 복사하지

못한 요소가 남아 있는 상태를 전제로 합니다. 커서 pb를 한 칸씩 진행하면서 복사하지 않은 모든 배열 b의 요소를

배열 c에 복사합니다.

​

☞ 병합에 필요한 시간 복잡도는 O(n) 입니다.

​

​

[병합 정렬]

1. 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합정렬(merge sort)이라고 합니다.

2. 병합 정렬 알고리즘의 순서를 정리하면 다음과 같습니다.

1) 배열의 요소 개수가 2개 이상인 경우

(1) 배열의 앞부분을 병합 정렬로 정렬합니다.

(2) 배열의 뒷부분을 병합 정렬로 정렬합니다.

(3) 배열의 앞부분과 뒷부분을 병합합니다.

☞ mergeSort 메서드는 병합한 결과를 일시적으로 저장할 작업용 배열인 buff를 생성합니다.

☞ 그런 다음 실제로 정렬 작업을 수행할 __mergerSort 메서드를 호출합니다.

☞ 병합 순서는 다음과 같이 3단계로 이루어집니다.

(1) 배열의 앞부분(a[left] ~ a[center])을 buff[0] ~ buff[center - left]에 복사합니다. for 문이 끝날 때

p의 값은 복사한 요소의 개수 center - left + 1이 됩니다.

(2) 배열의 뒷부분(a[center + 1] ~ a[right]) 과 buff 로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 a에

저장합니다.

(3) 배열 buff에 남아 있는 요소를 배열 a에 복사합니다.

☞ 배열 병합의 시간 복잡도는 O(n) 이고 데이터의 요소 개수가 n개 일 때, 병합 정렬의 단계는 log n 만큼 필요하므로

전체 시간 복잡도는 O(n log n)이라고 할 수 있습니다.

☞ 병합 정렬은 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬방법이라고 할 수 있습니다.

​