[DataStruct] Merge

What

• 시간복잡도 O(n log n)이지만 메모리를 퀵소트에 비교적 많이 사용된다는 점이 단점이다. 동작원리를 보자보자

동작원리

전반적 코드 흐름

1. 쪼개기 ….

2. 쪼개는 구간이 없으면 새로운 배열을 생성해 정렬하자

 

How

Why

• Java를 쓰게 되면 Arrays.sort, Collections.sort 라는 메소드의 동작원리의 기반이 되는 정렬(dual-pivot quick sort, 혹은 TimSort(mergeSort + quickSort) )이다. 사용하는데 모르고 있어도 크게 상관 없지만 이처럼 라이브러리를 사용하면서 원리를 안다는 것은 좋은 습관이기 때문이다.

Code

import java.util.Arrays;
import java.util.Scanner;

public class MergeSort {
	static int left[];
	static int right[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(sc.nextLine());
		}

		divide(0, arr.length - 1, arr);

		Arrays.stream(arr).forEach(System.out::println);
	}

	public static void divide(int s, int e, int[] arr) {
		if (e - s < 1)
			return;
		int mid = (s + e) >> 1;
		divide(s, mid, arr);
		divide(mid + 1, e, arr);
		int[] temp = new int[e - s + 1];
		int tIdx = 0;
		int leftIdx = s;
		int rightIdx = mid + 1;

		while (leftIdx <= mid && rightIdx <= e) {
			if (arr[leftIdx] < arr[rightIdx]) {
				temp[tIdx++] = arr[leftIdx++];
			} else {
				temp[tIdx++] = arr[rightIdx++];
			}
		}

		while (leftIdx <= mid) {
			temp[tIdx++] = arr[leftIdx++];
		}

		while (rightIdx <= e) {
			temp[tIdx++] = arr[rightIdx++];
		}
		
		tIdx = 0;
		for (int i = s; i <= e; i++) {
			arr[i] = temp[tIdx++];
		}
	}
}

 REFER

합병 정렬(=병합 정렬) 이란?

1. 합병 정렬 1-1. 합병 정렬? 병합 정렬? 1-2. 합병 정렬이란? 1-3. 움짤로 보는 예시 1-4. 글로 보는 예시 1-5. 소스코드 1-6. 합병 정렬의 시간 복잡도 1-7. 합병 정렬은 얼마나 빠를까? 1. 합병 정렬 1-1. 합병 정렬? 병합 정렬? 처음에 이름이 굉장히 헷갈렸다. (합병이 병합이고 병합이 합병 아닌가...? 🥴) 결론부터 말하자면 둘 다 맞는 말이다. 둘 다 사용해도 된다. 개인적으로 궁금해서 둘의 그 미묘한 차이를 알고 싶어 알아봤는데 합병: A와 B가 합쳐져 C가 만들어짐 병합: A가 B의 일부가 되거나 B가 A의 일부가 됨 이 블로거에 의하면 위와 같은 차이가 있다고 한다. 만약 이게 사실이라면 음,,, 나는 합병 정렬이 오늘 배울 내용과 더 적합하지 않을까..?라..

https://todaycode.tistory.com/54?category=997273

2750번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

https://www.acmicpc.net/problem/2750