- 자바코드로 구현한 병합정렬
package day0322_분할정복;
import java.util.Arrays;
public class 병합정렬 {
static int[] arr;
static int[] result;
public static void main(String[] args) {
arr = new int[] {3, 1, 4, 6, 9, 2, 8, 7, 5};
result = new int[arr.length];
sort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(result));
}
public static void sort(int[]arr, int left, int right) {
if(left>=right) return;
//분할과정
sort(arr, left, (left+right)/2);
sort(arr, (left+right)/2+1, right);
//합치기
merge(arr, left, right);
}
public static void merge(int[] arr, int left, int right) {
//가운데 값을 기준으로 왼쪽은 left포인터, 오른쪽은 right포인터를 보며 합쳐나갈 것.
int m = (left+right)/2 ;
//왼쪽 포인터
int i = left;
//오른쪽 포인터
int j = m+1;
//결과 값 배열의 index
int idx = left;
//왼쪽 포인터가 왼쪽배열 범위를, 오른쪽 포인터가 오른쪽 배열 범위를 벗어나지 않을 때 실행
while(i<=m && j<=right) {
//왼쪽이 작으면 왼쪽포인터가 가리키는 값을 결과에 넣고 포인터++
if(arr[i]<=arr[j]) {
result[idx++] = arr[i];
i++;
//오른쪽이 클 때는 반대로!
}else {
result[idx++] = arr[j];
j++;
}
}
//왼쪽 또는 오른쪽 배열의 숫자를 모두 털어내고 난 후!
//아래 두개의 for문을 돌면, 둘 중에 비어있는 쪽의 for문만 동작
//남아 있는 배열 털어내기!!
//i가 m+1이 됐다면(다 털어냈다면) 해당 for문 동작x
for(int k=i; k<m+1; k++) {
result[idx++] = arr[k];
}
//오른쪽도 마찬가지
for(int k=j; k<=right; k++) {
result[idx++] = arr[k];
}
//결과값에 넣은 모든 배열을 다시 원래 배열에 넣기(정렬된 결과 넣기!)
for(int k=left; k<=right; k++) {
arr[k] = result[k];
}
}
}
'Learning-log -CS > Data Structure & Algorithm' 카테고리의 다른 글
알고리즘 - 이분탐색(Binary Search)과 매개변수 탐색(Parameter Search) (Java, Python) (0) | 2023.04.20 |
---|---|
알고리즘 - 퀵정렬 (0) | 2023.03.27 |
알고리즘 - 백트래킹&순열 (0) | 2023.03.27 |
알고리즘 - 조합 (0) | 2023.03.26 |
알고리즘 - 부분집합 (0) | 2023.03.26 |