[BOJ/Step12] 2751 : 수 정렬하기 2 (JAVA)

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

---

문제

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

---

풀이

시간복잡도가 O(nlogn)인 정렬 알고리즘으로 풀라고 명시

=> 합병 정렬 알고리즘

=> 힙 정렬 알고리즘

import java.io.*;
import java.util.Scanner;

public class B2751 {
	
	static int[] buff;
	
	static void mergeSort(int[] a, int left, int right) {
		if(left < right) {
			int i;
			int center = (left + right) /2;
			int p = 0;
			int j = 0;
			int k = left;
			
			mergeSort(a, left, center);
			mergeSort(a, center + 1, right);
			
			for(i = left; i <= center; i++)
				buff[p++] = a[i];

			while(i <= right && j < p)
				a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
					
			while(j < p)
				a[k++] = buff[j++];
		}
	}
	
	static void mergeSort(int[] a, int n) {
		buff = new int[n];
		mergeSort(a, 0, n-1);
		buff = null;
	}
	
	static void swap(int[]a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	
	static void downHeap(int[] a, int left, int right) {
		int temp = a[left];
		int child;
		int parent;
		
		for(parent = left; parent <(right+1)/2; parent = child) {
			int cl = parent * 2 +1;
			int cr = cl + 1;
			child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
			if(temp >= a[child])
				break;
			a[parent] = a[child];
		}
		a[parent] = temp;
	}
	
	static void heapSort(int[] a, int n) {
		for(int i = (n-1)/2; i >= 0; i--)
			downHeap(a, i, n - 1);
		
		for(int i = n-1; i > 0; i--) {
			swap(a, 0, i);
			downHeap(a, 0, i-1);
		}
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = sc.nextInt();
		int[] sort = new int[n];
		
		for(int i = 0; i < n; i++) {
			sort[i] = sc.nextInt();
		}
		
		mergeSort(sort, n);		// 합병 정렬
		//heapSort(sort, n);	// 힙 정렬
		
		
		for(int i = 0; i < n; i++) {
			bw.write(Integer.toString(sort[i]) +"\n");
		}
		bw.flush();
	}
}