[Java] Merge Sort (병합정렬)알고리즘/정렬2023. 8. 13. 13:13
Table of Contents
반응형
설명
1) 리스트의 길이가 1이 될 때 까지 나눈다(mergeSort())
2) 왼쪽과 오른쪽 리스트를 대소 비교 하여 정렬된 결과(merge()) 반환
- 재귀 함수 호출하여 작은 문제로 나눈 후 큰 문제의 정답을 구한다
- 재귀 호출로 인해 스택 오버플로우 발생가능(단점)
- Java의 경우 인스턴스 메서드 *.subList(int from, int to) 사용하여 쉽게 리스트 분할 가능하다
시간 복잡도 : O(NlogN)
- 파티션을 나누는데 logN 만큼 걸리고, 다시 병합할 경우 N 만큼의 소요
공간 복잡도 : O(N)
영상 참고
https://www.youtube.com/watch?v=3j0SWDX4AtU
작은 문제로 나눠서 큰 문제의 해답을 구한다
코드
- 오름차순 정렬 기준으로 작성
- 내림차순의 경우 merge 조건문 수정하면 됨
import java.util.*;
public class Main {
private static List<Integer> mergeSort(List<Integer> data) {
if(data.size() <= 1) return data;
int mid = data.size() / 2;
List<Integer> left = mergeSort(data.subList(0, mid));
List<Integer> right = mergeSort(data.subList(mid, data.size()));
return merge(left, right);
}
private static List<Integer> merge(List<Integer> left, List<Integer> right) {
List<Integer> result = new ArrayList<>();
int L = 0;
int R = 0;
while(L < left.size() && R < right.size()) {
if(left.get(L) < right.get(R)) {
result.add(left.get(L++));
} else {
result.add(right.get(R++));
}
}
while(L < left.size()) {
result.add(left.get(L++));
}
while(R < right.size()) {
result.add(right.get(R++));
}
return result;
}
public static void main(String[] args) {
List<Integer> data = new ArrayList();
for(int i = 1; i <= 10; i++) {
data.add((int)(Math.random() * 100));
}
// 병합 정렬
System.out.println(mergeSort(data));
}
}
정렬 전 : [22, 15, 34, 57, 11, 38, 85, 70, 69, 7]
정렬 후 : [7, 11, 15, 22, 34, 38, 57, 69, 70, 85]
반응형
'알고리즘 > 정렬' 카테고리의 다른 글
[Java] Quick Sort(퀵 정렬, 재귀 방식, 왼쪽/중간/오른쪽 피벗) (0) | 2023.08.13 |
---|---|
[BOJ 15970] 화살표 그리기 (java) (0) | 2023.06.01 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!