[2751] 수 정렬하기 2 (JAVA)

# 문제 설명

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

---

입력

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

---

출력

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

 

# 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); //배열의 크기

        int[] A = new int[N];
        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            A[n] = Integer.parseInt(st.nextToken());
        }

        mergeSort(A, 0, N-1);

        for (int a : A) {
            sb.append(a + "\n");
        }

        System.out.print(sb);
    }

    public static void mergeSort(int[] arr, int start, int end) {
        if (start < end) {
            int middle = (start + end) / 2;
            mergeSort(arr, start, middle);
            mergeSort(arr, middle+1, end);
            merge(arr, start, middle, end);
        }
    }

    public static void merge(int[] arr, int start, int middle, int end) {
        int[] tmp = new int[end-start+1];
        int p1 = start; //집합1 포인터
        int p2 = middle+1; //집합2 포인터
        int tmp_p = 0; //tmp 포인터

        while (p1 <= middle && p2 <= end) {
            if (arr[p1] <= arr[p2]) {
                tmp[tmp_p++] = arr[p1++];
            }
            else {
                tmp[tmp_p++] = arr[p2++];
            }
        }

        while (p1 <= middle) {
            tmp[tmp_p++] = arr[p1++];
        }

        while (p2 <= end) {
            tmp[tmp_p++] = arr[p2++];
        }

        p1 = start;
        tmp_p = 0;

        while (p1 <= end) {
            arr[p1++] = tmp[tmp_p++];
        }
    }
}

 

병합 정렬을 이용하여 배열을 오름차순 정렬했다.

 

mergeSort 함수에 정렬할 배열, 시작 위치, 끝 위치를 입력하여 병합 정렬을 실행한다.

start가 end보다 작으면, 중간 위치 middle을 구하고 start~middle, middle+1~end까지 구간을 나눠 병합 정렬을 실행한다.

 

merge 함수에 정렬할 배열, 시작위치, 중간 위치, 끝 위치를 입력하여 병합을 실행한다.

병합된 데이터를 저장할 배열 tmp를 end-start+1 크기로 만든다.

집합1, 집합2, tmp의 포인터를 각각 만든다.

 

p1이 middle보다 작거나 같고 p2가 end보다 작거나 같을 때까지 반복하면서 p1과 p2가 가리키는 값 중 최솟값을 tmp에 저장한다.

반복문이 끝나고 p1 또는 p2에 남은 값들을 모두 tmp로 옮겨준다.

 

p1을 start로 설정하고 tmp_p를 0으로 설정한 후, tmp에 있는 값들을 기존 배열 arr로 옮긴다.

 

오름차순 정렬된 데이터를 출력한다.