[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)인 정렬 알고리즘으로 풀라고 명시

=> 합병 정렬 알고리즘

=> 힙 정렬 알고리즘

java

닫기 줄바꿈

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();
‌}
}