Java 프로그래밍에서 병합 정렬 알고리즘을 실현하는 실례 강좌
병합 정렬은'분치'(divide and conquer) 라고 불리는 정책을 기반으로 한다.그 기본적인 사고방식은 다음과 같다.
1. 두 개의 질서정연한 수조를 하나의 질서정연한 수조로 합치려면 다음과 같은 코드를 쉽게 쓸 수 있다.
//both a and b is ascend.
public void merge(int[] a, int[] b, int[] c){
int i=0,j=0,k=0;
while (i<=a.length && j<=b.length){
if (a[i]<=b[i]){
c[k++]=a[i++];
}
else{
c[k++]=b[j++];
}
}
while (i<=a.length){
c[k++]=a[i++];
}
while (j<=b.length){
c[k++]=b[j++];
}
}
2. 만약에 무질서한 수조가 정렬을 필요로 하지만 완전히 구분된 두 개의 서브수조 A와 B가 각각 정렬되어 있다면 상술한 코드를 빌려 우리도 쉽게 실현할 수 있다.
3. 그렇다면 A, B가 무질서하면 어떻게 하나요?그것들을 더 작은 수조로 나눌 수 있다.
4. 이렇게 최소로 나누면 모든 하위 그룹은 하나의 원소만 있고 질서수 그룹으로 볼 수 있다.
5. 이 가장 작은 수조부터 위의 절차를 거슬러 합치면 전체 수조가 배열된다.
요컨대 병합 정렬은 병합을 사용하는 것이다. 먼저 수조를 서브수조로 분해한 다음에 수조를 병합하는 것이다.
예제
다음은 예를 들어 만약에 수조 a={2,1,3,5,2,3}를 정렬하려면 수조를 {2,1,3}과 {5,2,3} 두 개의 서브수조로 나누면 이 두 서브수조가 정렬된 후에 {1,2,3}와 {2,3,5}로 변한 다음에 이 두 개의 서브수조를 통합하여 조작하면 최종 질서수조를 얻을 수 있다.코드는 다음과 같습니다.
void sort(int[] a) {
int[] aux = new int[a.length]; //
mergeSort(a, 0, a.length - 1, aux);
}
void mergeSort(int[] a, int lo, int hi, int[] aux) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid, aux);
mergeSort(a, mid + 1, hi, aux);
merge(a, lo, mid, hi, aux);
}
void merge(int[] a, int lo, int mid, int hi, int[] aux) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
if (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (aux[i] <= aux[j])
a[k] = aux[i++];
else
a[k] = aux[j++];
}
}
위의 실현에서 하나의 큰 문제를 작은 문제로 나누어 각각 해결한 다음에 모든 작은 문제의 답안으로 전체 큰 문제를 해결하는 것과 같다.큰 그룹의 정렬을 작은 그룹의 정렬로 나누는 것은 위에서 아래로 정렬하는 것이다.또 하나의 실현은 밑에서 위로 올라가는 정렬이다. 즉, 먼저 두 개를 합친 다음에 네 개를 합친 것이다.코드는 다음과 같습니다.
void sort(int[] a) {
int N = a.length;
int[] aux = new int[N];
for (int sz = 1; sz < N; sz += sz) {
for (int lo = 0; lo < N - sz; lo += sz + sz) {
// ，
merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
