병합 정렬
- 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
- 시간 복잡도는 O(nlogn)이다.
병합 정렬 과정
- 최초에 가장 작은 그룹으로 나눈다.
- 2개씩 그룹을 합치며 오름차순 정렬한다.
- 다시 2개씩 그룹을 합치며 정렬한다.
- 위의 과정을 거치면 그룹 전체의 오름차순 정렬이 완료된다.
2개의 그룹을 병합하는 과정
- 투 포인터 개념을 사용하여 왼족, 오른쪽 그룹을 병합한다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.
문제 풀이
https://yurison.tistory.com/344
[백준/자바] 2751 - 수 정렬하기 2
import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Buf
yurison.tistory.com
https://yurison.tistory.com/543
[백준/자바] 1517 - 버블 소트
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int[] arr, temp; public static long result; public static void main(String[] args) throws IOExc
yurison.tistory.com
'공부 기록 > 알고리즘' 카테고리의 다른 글
| Do it! 알고리즘 코딩테스트 with JAVA - (13) DFS(깊이 우선 탐색) (0) | 2023.08.04 |
|---|---|
| Do it! 알고리즘 코딩테스트 with JAVA - (12) 기수 정렬 (0) | 2023.08.03 |
| Do it! 알고리즘 코딩테스트 with JAVA - (10) 퀵 정렬 (0) | 2023.08.02 |
| Do it! 알고리즘 코딩테스트 with JAVA - (9) 삽입 정렬 (0) | 2023.08.02 |
| Do it! 알고리즘 코딩테스트 with JAVA - (8) 선택 정렬 (0) | 2023.08.02 |
