* 병합 정렬
정렬의 마친 두 배열을 병합하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다.
1. 정렬을 마친 두 배열을 병합하기
public class MergeArray {
//정렬을 마친 배열 a, b를 병합하여 배열 c에 저장
static void merge(int[] a, int na, int[] b, int nb, int[] c) {
int pa = 0;
int pb = 0;
int pc = 0;
while (pa < na && pb < nb) //작은 값을 c 배열에 저장한다.
c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
while (pa < na) //a에 남아있는 요소를 복사
c[pc++] = a[pa++];
while (pb < nb) //b에 남아있는 요소를 복사
c[pc++] = a[pb++];
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
int[] a = {2, 4, 6, 11, 13};
int[] b = {1, 2, 3, 4, 9, 16, 21};
int[] c = new int[13];
System.out.println("두 배열의 병합");
merge(a, a.length, b, b.length, c); //배열 a와 b를 병합하여 c에 저장
System.out.println("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
System.out.println("배열 a : ");
for (int i = 0; i < a.length; i++) {
System.out.print("a[" + i + "] = " + a[i]);
}
System.out.println("배열 b : ");
for (int i = 0; i < b.length; i++) {
System.out.print("b[" + i + "] = " + b[i]);
}
System.out.println("배열 c : ");
for (int i = 0; i < a.length; i++) {
System.out.print("c[" + i + "] = " + c[i]);
}
}
}
2. 1번을 응용하여 분할 정복법에 따라 병합 정렬하기
배열을 2등분하여 앞부분과 뒷부분으로 나눈다.
앞부분과 뒷부분을 각각 정렬하고 병합한다.
여기서 재귀호출을 하게 되는데 그 앞부분과 뒷부분도 또다시 병합정렬을 이용하기 때문이다.
public class MergeSort {
static int[] buff; //작업용 배열
//a[left] ~ a[right] 을 재귀적으로 병합 정렬한다.
static void __mergeSort(int[] a, int left, int right) {
if (left < right) {
int i;
int center = (left + right) / 2;
int p = 0;
int j = 0;
int k = left;
__mergeSort(a, left, center); //배열의 앞부분을 병합 정렬한다.
__mergeSort(a, center + 1, right); //배열의 뒷부분을 병합정렬한다.
for (i = left; i <= center; i++) //버퍼에다 a[left]~a[center]를 복사한다.
buff[p++] = a[i];
while (i <= right && j < p) //버퍼와, a배열(center 뒷부분부터 right까지)을 서로 병합정렬한다.
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
while (j < p) //buff의 나머지 요소를 배열 a에 복사한다.
a[k++] = buff[j++];
}
}
//병합 정렬
static void mergeSort(int[] a, int n) {
buff = new int[n]; //작업용 배열 생성
__mergeSort(a, 0, n - 1); //배열 전체를 병합 정렬한다.
buff = null; //작업용 배열 해제
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("병합 정렬");
System.out.print("요솟수:");
int nx = stdIn.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "] : ");
x[i] = stdIn.nextInt();
}
mergeSort(x, nx);
System.out.println("오름차순으로 정렬했습니다.");
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]= " + x[i]);
}
}
}
3. 자바가 제공하는 sort 사용하기
- 기본 자료형 정렬
public class ArraySortTester {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수 : ");
int num = stdIn.nextInt();
int[] x = new int[num];
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "] :");
x[i] = stdIn.nextInt();
}
//sort 메소드는 기본 자료형의 배열을 정렬한다.
//퀵 정렬 알고리즘을 개선한 것으로 안정적이지 않다.
//즉 배열에 같은 값이 존재하는 경우 같은 값 사이의 순서가 바뀔 수 있다.
Arrays.sort(x);
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "] :");
}
}
}
- 클래스 객체 배열의 정렬 (병합 정렬)
클래스 객체 배열의 정렬에서 사용하는 알고리즘은 병합 정렬을 개선한 것으로 안정적인 결과가 보장된다.
아래 메소드들은 기본 오름 차순 정렬이다.
static void sort(Object[] a)
static void sort(Object[] a, int fromIndex, int toIndex) : fromIndex 부터 toIndex 까지만 정렬한다.
public class SortCalendar {
public static void main(String[] args) {
GregorianCalendar[] x = {
new GregorianCalendar(2017, Calendar.NOVEMBER, 1),
new GregorianCalendar(1963, Calendar.OCTOBER, 18),
new GregorianCalendar(1985, Calendar.APRIL, 5),
};
Arrays.sort(x);
for (int i = 0; i < x.length; i++)
System.out.printf("%04d년 %02d월 %02d일\n",
x[i].get(Calendar.YEAR),
x[i].get(Calendar.MONTH) + 1,
x[i].get(Calendar.DATE)
);
}
}
결과 출력
1963년 10월 18일
1985년 04월 05일
2017년 11월 01일
만약 정렬 시에 원하는 기준이 있을 경우 그 키를 기준으로 하는 Comparator를 구현 하면 된다.
아래 메소드들은 기본 오름 차순 정렬이다.
static void sort(T[] a, Comparator c)
static void sort(T[] a, int fromIndex, int toIndex, Comparator c) : T를 부모로 갖는 클래스이어야 한다.
public class PhyscExamSort {
static class PhyscData {
String name;
int height;
double vision;
PhyscData(String name, int height, double vision) {
this.name = name; this.height = height; this.vision = vision;
}
public String toString() {
return name + " " + height + " " + vision;
}
//키 오름차순용 comparator
//Comparator의 compare 메소드를 오버라이드하여 기준을 정함.
static final Comparator HEIGHT_ORDER = new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator {
@Override
public int compare(PhyscData d1, PhyscData d2) {
return (d1.height > d2.height) ? 1 :
(d1.height < d2.height) ? -1 : 0;
}
}
}
public static void main(String[] args) {
PhyscData[] x = {
new PhyscData("이나령", 162,0.3),
new PhyscData("전서현", 122,1.3),
new PhyscData("홍길동", 172,0.8),
new PhyscData("유지훈", 182,0.9),
};
Arrays.sort(x, PhyscData.HEIGHT_ORDER); //HEIGHT_ORDER 를 사용하여 정렬한다.
}
}
