Data Structure/Data Structure 구현

머지소트(MergeSort) 구현해보기 JAVA(자바)

100win10 2020. 3. 9. 15:30

병합 정렬은 분할 정복이라는 알고리즘에 근거하여 만들어진 정렬 방법이다.

 

우선은 분할의 과정으로 데이터를 둘로 나누고 하나씩 구분이 될 때까지 진행을 한다.

 

분할이 완료되었다면 작은 순서대로 하나씩 b 배열에 추가해서 순서를 맞추고 a배열에 넣어준다.

 

별도의 배열이 하나 더 필요하다는 특징이 있다.

 

 

public class main {
public static void main(String[] args) {
int[] a = new int[4];
a[0] = 3;
a[1] = 1;
a[2] = 5;
a[3] = 4;
mergeSort(a, 0, 3);
for(int A : a)
System.out.print(A + " ");
}
private static void mergeSort(int[] a, int left, int right) {
if(left < right) {
int mid = (left + right) / 2;
mergeSort(a,left,mid);
mergeSort(a,mid+1,right);
merge(a,left,mid,right);
}
}
private static void merge(int[] a, int left, int mid, int right) {
int lidx = left;
int ridx = mid+1;
int[] b = new int[a.length];
int bidx = left;
while(lidx <= mid && ridx <= right) {
if(a[lidx] <= a[ridx]){
b[bidx] = a[lidx];
lidx += 1; bidx +=1;
}
else {
b[bidx] = a[ridx];
ridx += 1; bidx +=1;
}
}
if(lidx > mid) {
for(int i = ridx; i<= right; ++i,++bidx)
b[bidx] = a[i];
}
else {
for(int i = lidx; i<= mid; ++i, ++bidx)
b[bidx] = a[i];
}
for(int i=left; i<=right; ++i)
a[i] = b[i];
}
}
view raw .java hosted with ❤ by GitHub