이번엔 합병정렬에서 3부분으로 나눠서 합병하는 소스를 보도록 합시다.
앞과 마찬가지로 자바로 작성했습니다.
소스가 좀 길죠?
별거 없습니다... 일단 나누는 부분은 앞서 이진검색에서 말했듯이 3부분으로 나눠서
1/3과 2/3나누는 것만 주의하면되고요. 2분할과 다른점은 매개변수를 하나 더 준 것 입니다.
아 한가지 더 중요한 것은 3분할을 할때에는 2개이하는 분할을 하지 못하므로
그상태에서 정렬을 해준다는 것입니다.!!
합병정렬에서는 2분할과 같은 원리로 돌아가지만. 주의해야할점이 있습니다.
3분할시에는 부분이 남는 경우의 수가 많습니다.
각 부분을 a b c 라고 하면
abc모두 존재할때, ab, bc, ac등 2개가 존재할때 a, b, c와 같이 단 하나만 존재할때로
나뉩니다. 이때에 대해서 다 나눠서 합병을 실시해줘야합니다~
앞과 마찬가지로 자바로 작성했습니다.
private void MergeSort(int i, int j){
int midLeft; // 배열의 1/3지점을 가르킴
int midRight; // 배열의 2/3지점을 가르킴
if ( j - i >= 2 ){ // 배열울 분할시 3개보다 적으면 분할하면안됨
midLeft = (int)(i*2+j)/3; // 지점 계산
midRight = (int)(i+j*2)/3;
MergeSort(i,midLeft); // 재귀적 순회
MergeSort(midLeft+1,midRight);
MergeSort(midRight+1,j);
Merge(i,midLeft,midRight,j); // 합병
}else{ // 배열 분할시 3개보다 적으면 그 2개를 정렬
if ( j - i == 1 && value[j] < value[i] ){
int temp = value[j];
value[j] = value[i];
value[i] = temp;
}
}
}
private void Merge(int low, int midLeft, int midRight, int high) {
int buf[] = new int[value.length]; // 임시배열
int h, i, j, k, l;
h = low; i = low; j = midLeft + 1; k = midRight + 1; l = high;
while ( h <= midLeft && j <= midRight && k <= high){
if ( value[h] <= value[j] ){ // 배열 3개가 모두 존재할 경우의 통합
if ( value[h] <= value[k] ){
buf[i] = value[h];
h++;
}else{
buf[i] = value[k];
k++;
}
}else{
if ( value[j] <= value[k] ){
buf[i] = value[j];
j++;
}else{
buf[i] = value[k];
k++;
}
}
i++;
}
if ( h > midLeft ){ // 배열 2개가 존재할 경우의 통합
while ( j <= midRight && k <= high ){
if ( value[j] < value[k] ){
buf[i] = value[j];
j++;
} else {
buf[i] = value[k];
k++;
}
i++;
}
} else if ( j > midRight ) {
while ( h<= midLeft && k<= high ){
if ( value[h] < value[k] ){
buf[i] = value[h];
h++;
} else {
buf[i] = value[k];
k++;
}
i++;
}
} else if ( k > high ) {
while ( h <= midLeft && j <= midRight ) {
if ( value[h] < value[j] ){
buf[i] = value[h];
h++;
} else {
buf[i] = value[j];
j++;
}
i++;
}
}
// 배열 한개가 존재할 경우의 통합
if ( h > midLeft && j > midRight ){
for ( ; k <= high ; k++ ){
buf[i] = value[k];
i++;
}
} else if ( j > midRight && k > high ){
for ( ; h <= midLeft ; h++ ){
buf[i] = value[h];
i++;
}
} else if ( k > high && h > midLeft ){
for ( ; j <= midRight ; j++ ){
buf[i] = value[j];
i++;
}
}
// 임시 배열(정렬된 배열)을 본 배열로 복사
for ( l = low ; l <= high ; l++ ){
value[l] = buf[l];
}
} 소스가 좀 길죠?
별거 없습니다... 일단 나누는 부분은 앞서 이진검색에서 말했듯이 3부분으로 나눠서
1/3과 2/3나누는 것만 주의하면되고요. 2분할과 다른점은 매개변수를 하나 더 준 것 입니다.
아 한가지 더 중요한 것은 3분할을 할때에는 2개이하는 분할을 하지 못하므로
그상태에서 정렬을 해준다는 것입니다.!!
합병정렬에서는 2분할과 같은 원리로 돌아가지만. 주의해야할점이 있습니다.
3분할시에는 부분이 남는 경우의 수가 많습니다.
각 부분을 a b c 라고 하면
abc모두 존재할때, ab, bc, ac등 2개가 존재할때 a, b, c와 같이 단 하나만 존재할때로
나뉩니다. 이때에 대해서 다 나눠서 합병을 실시해줘야합니다~