지난 글 : [알고리즘/Do it 알고리즘] - 퀵 정렬
정렬을 마친 두 배열의 병합
먼저 정렬을 마친 두 배열의 병합(merge)을 살펴보자. 각 배열에서 선택한 요솟값을 비교한 뒤 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복해 정렬을 마친 배열을 만든다.
a: 2 4 6 8 11 13
===========================================================================
b: 1 2 3 4 9 16 21
===========================================================================
c: 1 2 2 3 4 4 6 8 9 11 13 16 21위 그림은 요솟수가 na인 배열 a와 요솟수가 nb인 배열 b를 병합해 배열 c에 저장한다. 이를 실행하는 메서드에서는 배열 a, b, c를 동시에 스캔한다. 각 배열의 작업에서 선택한 요소의 인덱스는 pa, pb,pc다. 이 인덱스를 저장한 변수를 커서라고 하자. 처음에는 첫 요소를 선택하므로 커서를 모두 0으로 초기화한다. 그 다음은 아래와 같다.
1)
1. 배열 a에서 선택한 요소(a[pa])와 b에서 선택한 요소(b[pb])를 비교해 작은 쪽 값을 c[pc]에 저장한다.
2. 위 배열에서는b[0]의 값이 a[0]보다 작으므로 b[0]인 1을 c[0]에 대입한다.
3. 그 후 커서 pb, pc를 한 칸 나아가도록 하고 pa는 그대로 둔다.
4. 이처럼 pa, pb가 가리키는 값을 비교해 적은 쪽 값을 c[pc]에 대입하고 꺼낸 쪽 커서와 pc를 한 칸 나아가는
작업을 반복한다.
5. 커서 pa가 a의 끝에 다다르거나 pb가 b의 끝에 다다르면 while문에서 빠져나와 작업을 종료한다.
2)
이 while문이 실행되는 것은 1)에서 배열 b의 모든 요소를 c로 복사했으나 배열 a에는 아직 복사하지 않은
요소가 남아 있는 경우다. 커서 pa를 한 칸씩 나아가며 복사하지 않은 모든 요소를 배열 c에 복사한다.
3)
이 while문이 실행되는 것은 1)에서 배열 a의 모든 요소를 c에 복사했으나 배열 b에 아직 복사하지 않은 요소가
남아 있는 경우다. 커서 pb를 한 칸씩 나아가며 복사하지 않은 모든 요소를 c에 복사한다.
병합 정렬 구현하기
정렬을 마친 배열의 병합을 응용해 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬(merge sort)이라 한다.
5 6 4 8 3 7 9 0 1 5 2 3
=========================================================================================
a(정렬 전): 5 6 4 8 3 7
-----------------------------------------------------------------------------------------
a(정렬 후): 3 4 5 6 7 8
=========================================================================================
b(정렬 전): 9 0 1 5 2 3
-----------------------------------------------------------------------------------------
b(정렬 후): 0 1 2 3 5 9
=========================================================================================
a와 b 배열을 병합 정렬:
0 1 2 3 3 4 5 5 6 7 8 9위 그림은 배열의 요솟수가 12개이므로 6개씩 두 부분으로 각각 나눈다. 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있다. 이 때, 앞부분과 뒷부분 6개 요소를 바로 정렬하지 않고 다시 병합 정렬을 적용한다.
9 0 1 5 2 3
===========================================================
a(정렬 전): 9 0 1
-----------------------------------------------------------
a(정렬 후): 0 1 9
===========================================================
b(정렬 전): 5 2 3
-----------------------------------------------------------
b(정렬 후): 2 3 5
===========================================================
a와 b를 병합 정렬:
0 1 2 3 5 9이 과정에서 만들어지는 앞부분({9, 0, 1})과 뒷부분({5, 2, 3})도 바로 정렬하지 않고 병합 정렬을 적용한다.
병합 정렬 알고리즘
병합 정렬 알고리즘의 순서를 정리하면 아래와 같다.
배열의 요솟수가 2개 이상인 경우
- 배열의 앞부분을 병합 정렬로 정렬한다.
- 배열의 뒷부분을 병합 정렬로 정렬한다.
- 배열의 앞부분과 뒷부분을 병합한다.
위 프로그램에서 mergeSort 메서드가 수행하는 내용은 아래와 같다.
A: 병합한 결과를 일시적으로 저장할 작업용 배열 buff를 생성한다.
B: 정렬 작업을 수행할 __mergeSort 메서드를 호출한다.
C: 작업용 배열을 해제한다.B에서 호출하는 __mergeSort 메서드가 실제 병합 정렬을 수행하는 메서드다. 이 __mergeSort 메서드는 a(정렬할 배열), left(첫 번째 요소의 인덱스), right(마지막 요소의 인덱스)를 인자로 전달받고 left가 right보다 작을 때만 동작한다. 이 메서드는 가장 먼저 앞부분(a[left] ~ a[center])과 뒷부분(a[center + 1] ~ a[right])에 대해 __mergeSort 메서드를 재귀 호출한다. 이렇게 재귀 호출을 반복하면 배열의 앞부분과 뒷부분이 각각 정렬을 마치게 된다.
정렬을 마친 앞부분과 뒷부분은 작업용 배열 buff를 사용해 병합한다. 병합을 수행하는 코드는 아래와 같다.
병합 순서는 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)이라 할 수 있다. 병합 정렬은 서로 떨어져 있는 요소를 교환하는 경우가 없기에 안정적인 정렬 방법이라 할 수 있다.
Arrays.sort로 퀵 정렬과 병합 정렬하기
이전에 배운 이진 검색에서 사용했던 binarySearch 메서드는 java.util.Arrays 클래스의 클래스 메서드로 제공된다. 이 클래스는 배열을 정렬하는 클래스 메서드 sort도 제공한다. sort 메서드의 다양한 형태 중 안정적인 정렬은 아래와 같다.
- static void sort(Object[] a)
- static void sort(Object[] a, int fromIndex, int toIndex)
- static <T> void sort(T[] a, Comparator<? super T> c)
- static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)위 메서드 외에 sort 메서드는 모두 배열 a를 오름차순으로 정렬한다.
기본 자료형 배열의 정렬(퀵 정렬)
sort 메서드 중 위에 작성한 4개의 메서드를 제외한 모든 메서드는 기본 자료형의 배열을 정렬한다. 이 sort 메서드의 내부에서 사용하는 알고리즘은 퀵 정렬 알고리즘을 개선한 것으로 안정적이지 않다. 즉, 배열에 같은 값이 존재하면 같은 값 사이의 순서가 뒤바뀔 수 있다. 아래는 자바가 제공하는 sort 메서드를 사용해 int형 배열을 정렬하는 프로그램이다.
클래스 객체 배열의 정렬(병합 정렬)
위에 안정적인 메서드라고 표기한 sort 메서드는 클래스 객체 배열을 정렬할 때 사용하는데, 크게 두 종류로 나눌 수 있다.
A) 자연스러운 순서를 갖고 있는 배열을 정렬
자연스러운 순서로 요소의 대소 관계를 비교 판단한다. Inter형 배열, String형 배열에 알맞다.
- static void sort(Object[] a)
- static void sort(Object[] a, int fromIndex, int toIndex)
B) 자연스러운 순서를 갖고 있지 않은 배열을 정렬
요소의 대소 관계를 판단할 때 comparator c를 사용한다.
- static <T> void sort(T[] a, Comparator<? super T> c)
- static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)
기본 자료형을 정렬하는 다른 메서드들과 달리 위 4개 메서드의 내부에서 사용하는 메서드의 알고리즘은 병합 정렬을 개선한 것으로 결과가 안정적이다.
자연스러운 순서를 갖고 있는 배열의 정렬 만들기
아래는 A) 메서드로 배열을 정렬하는 프로그램이다.
이 프로그램은 GregorianCalendar형 배열 x를 정렬한다. 프로그램을 실행하면 날짜의 오름차순으로 정렬된다. GregorianCalendar 클래스는 Comparable 인터페이스와 compare To 메서드를 구현하고 있다. GregorianCalendar 클래스는 1 ~ 12월을 0 ~ 11로 표현하기에, get(MONTH)로 얻는 값은 0 ~ 11이므로 화면에 출력할 때는 1을 더한다.
자연스러운 순서를 갖고 있지 않은 배열의 정렬 만들기
아래는 B) 메서드로 정렬하는 프로그램이다. sort 메서드에서 두 번째 매개변수로 전달하는 comparator를 만드는 방법은 binarySearch 메서드와 같다. 이 프로그램은 클래스 PhyscData 내부에서 키의 오름차순으로 비교하기 위한 comparator를 정의한 뒤, 그 것을 사용해 정렬을 수행하고 있다. 프로그램을 실행하면 배열 x가 키의 순서로 정렬된다.
참고 서적 :
