1. 오늘 학습한 내용
백준 정렬(병합정렬) 문제 2751번
2. 알게 된 내용
병합정렬이란?
병합정렬(merge sort)이란 배열 형태로 되어 있는 값들을 2등분씩 자르면서 각 분할 부분이 각각 두 요소로만 구성될 때까지 진행하고, 그 작은 분할 안에서 정렬을 진행 + 두 묶음씩 다시 병합하는 방식이다. 정렬을 진행할 때에는 각 분할의 맨 앞 요소를 비교하면서 더 작은 값을 결과 배열에 차곡차곡 쌓으면서 진행한다.
병합정렬의 코드
// 메인 메서드에서 호출할 때는 arr 배열만 인자로 담아서 호출한다
private static void mergeSort(int[] arr) {
int[] tmp = new int[arr.length];
mergeSort(arr,tmp,0,arr.length-1);
}
// 같은 메서드이름이지만 매개변수가 다르다.
// 병합정렬을 하기 위해 분할하고 merge 메서드를 호출하는 역할
private static void mergeSort(int[] arr, int[] tmp, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(arr,tmp,start,mid); // 앞쪽
mergeSort(arr,tmp,mid+1,end); // 뒤쪽
merge(arr,tmp,start,mid,end);
}
}
// 분할된 배열을 가지고 실제로 정렬을 진행하는 역할
private static void merge(int[] arr, int[] tmp, int start, int mid, int end) {
for (int i = start; i <= end; i++) {
tmp[i] = arr[i];
}
int part1 = start; // 앞쪽 분할 배열의 시작점
int part2 = mid + 1; // 뒤쪽 분할 배열의 시작점
int index = start; // 작은 수를 새로 넣을 자리의 인덱스
while (part1 <= mid && part2 <= end) {
if (tmp[part1] <= tmp[part2]) { // 잎쪽 분할 배열의 시작점 값이 작으면
arr[index] = tmp[part1]; // arr배열에 앞쪽 분할 배열 시작점 값을 대입
part1++; // 앞쪽 분할 배열 시작점 뒤로 이동
} else {
arr[index] = tmp[part2];
part2++;
}
index++; // arr배열의 인덱스 증가
}
for (int i = 0; i <= mid - part1; i++) { // 앞쪽 분할 배열에서 데이터가 남아있는 경우
arr[index + i] = tmp[part1 + i];
}
// 뒤쪽 분할 배열에서 데이터가 남아있는 경우는 최종 배열 arr 뒤쪽에 이미 남아있으므로 따로 구현 x
}출처 : https://www.youtube.com/watch?v=QAyl79dCO_k (설명이 좋다)
+) 참고할 글
https://www.acmicpc.net/board/view/31887
3. 느낀 점
병합 정렬을 구현하기가 조금 어렵게 느껴져서 (실제로 배열을 여러개 만들어야 하나 싶어서 난감했다) 다른 분의 설명을 보면서 이해하고 참고하면서 풀었는데 내가 스스로 구현하기가 아직은 어려운 것 같지만.. 그래도 다음에 병합정렬을 이용해서 풀 때 오늘 알게 된 이 원리를 통해 조금이라도 스스로 구현해볼 수 있으면 좋겠다!
기록하자
0개의 댓글
