백준 JAVA11 2751번 : 수 정렬하기2

Mention : 병합정렬(Merge sort) 구현, Divide and Conquer

수 정렬하기 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	230355	66376	46185	30.478%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5
5
4
3
2
1

예제 출력 1

1
2
3
4
5

출처

• 데이터를 추가한 사람: ho94949, pichulia

슈도코드

N(정렬할 수 개수)
A(정렬할 배열)
for(N만큼){
	A를 채워준다.
}
병합정렬 함수 실행
출력

병합정렬 함수
병합정렬(start,end){
	start(시작점), end(종료점), mid(중간점)
	//재귀함수 형태로
	병합정렬(start,mid)
	병합정렬(mid+1, end)
	for(start~end) {
		temp배열 저장
	}
	//두 그룹을 병합하는 로직
	index1 앞쪽그룹 시작점 인덱스
	index2 뒤쪽그룹 시작점 인덱스
	while(index1 <= 중간점 && index2 <= 종료점) {
		양쪽 그룹의 index가 가르키는 값을 비교한 후 더 작은 수를 배열에 저장
			더 작은수가 있는 그룹의 index를 오른쪽으로 이동
			반복문이 끝난 후 데이터 정리
	}
}

Code

package sort;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class MergeSort_1 {
	public static int[] A, temp;
	public static long result;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		A = new int[N + 1];
		temp = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			A[i] = Integer.parseInt(br.readLine());
		}

		mergeSort(1, N);
		for (int i = 1; i <= N; i++) {
			bw.write(A[i] + "\n");
		}
		bw.flush();
		bw.close();
	}

	private static void mergeSort(int start, int end) {
		if (end - start < 1) {
			return;
		}
		int mid = start + (end - start) / 2;
		mergeSort(start, mid);
		mergeSort(mid + 1, end);
		for (int i = start; i <= end; i++) {
			temp[i] = A[i];
		}

		int j = start;
		int index1 = start;
		int index2 = mid + 1;
		while (index1 <= mid && index2 <= end) {
			if (temp[index1] > temp[index2]) {
				A[j] = temp[index2];
				j++;
				index2++;
			} else {
				A[j] = temp[index1];
				j++;
				index1++;
			}
		}
		while (index1 <= mid) {
			A[j] = temp[index1];
			j++;
			index1++;
		}
		while (index2 <= end) {
			A[j] = temp[index2];
			j++;
			index2++;
		}
	}
}