반응형
5. Merge Sorting
Merge정렬도 기본적으로 Divide and Conquor 방법으며 Recursive한 함수 호출 방식으로 구현한다. 아래와 같이 동작하며 수행 시간은 O(NlogN)이다
자바로 구현된 소스는 다음과 같다.
public static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
// base case
if (hi - lo <= 1) return;
// sort each half, recursively
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid, hi);
// merge back together
merge(a, aux, lo, mid, hi);
}
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
int i = lo, j = mid;
for (int k = lo; k < hi; k++) {
if (i == mid) aux[k] = a[j++];
else if (j == hi) aux[k] = a[i++];
else if (a[j].compareTo(a[i]) < 0) aux[k] = a[j++];
else aux[k] = a[i++];
}
// copy back
for (int k = lo; k < hi; k++)
a[k] = aux[k];
}
public static void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
sort(a, aux, 0, N);
}
// base case
if (hi - lo <= 1) return;
// sort each half, recursively
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid, hi);
// merge back together
merge(a, aux, lo, mid, hi);
}
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
int i = lo, j = mid;
for (int k = lo; k < hi; k++) {
if (i == mid) aux[k] = a[j++];
else if (j == hi) aux[k] = a[i++];
else if (a[j].compareTo(a[i]) < 0) aux[k] = a[j++];
else aux[k] = a[i++];
}
// copy back
for (int k = lo; k < hi; k++)
a[k] = aux[k];
}
public static void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
sort(a, aux, 0, N);
}
Divide and Conquor 방법 및 Recursion을 이용하여 코드도 깔끔하다
반응형
