Merge Sort (병합 정렬)

태그

정렬

알고리즘

백준 2751 수 정렬하기 2

www.acmicpc.net

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

수의 개수가 이전보다 커졌기 때문에 일반적인 정렬방식 말고, 다른 방식을 찾아야 한다.

병합 정렬의 특징

•

Array 로 값을 받은 경우, 정렬 시 임시 배열이 필요하다.

◦

제자리 정렬이 아니다.

•

안정적이다.

•

만약 배열의 크기가 크다면 연결 리스트를 사용하자.

병합 정렬의 순서

•

하나의 리스트를 두 개의 균등한 크기로 분할한다. (분할)

•

분할된 부분 리스트를 정렬한다. 부분 배열의 크기가 작지 않으면 다시 분할을 한다. (정복)

•

정렬된 부분 배열을 하나의 배열에 합병한다. (결합)

◦

이 단계에서 정렬이 이루어진다.

분할 정복에 관한 포스트: Divide and Conquer

문제 풀이

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

public class PROB2751 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int[] numbers;
    static int[] mergedNumbers;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        numbers = new int[N];
        mergedNumbers = new int[N];

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

        mergeSort(0, N - 1);

        for (int number : numbers) {
            sb.append(number).append("\n");
        }

        System.out.println(sb.toString());
    }

    public static void mergeSort(int low, int hight) { // 배열을 나눈다. 이는 원소의 개수가 2 인 경우만 진행
        if (low < hight) {
            int mid = (low + hight) / 2;
            mergeSort(low, mid);
            mergeSort(mid + 1, hight);
            merge(low, mid, hight);
        }
    }

    public static void merge(int low, int mid, int hight) { // 배열을 병합한다. 여기에서 정렬이 일어난다.
        int i = low;
        int j = mid + 1;
        int k = low;

        while(i <= mid && j <= hight) {
            if (numbers[i] <= numbers[j])
                mergedNumbers[k++] = numbers[i++]; // 첫번째 리스트 내의 원소가 더 작은 경우
            else
                mergedNumbers[k++] = numbers[j++]; // 두번재 리스트 내의 원소가 더 작은 경우
        }

        while(i <= mid) // 첫번째 리스트 내 원소가 남아있다면
            mergedNumbers[k++] = numbers[i++]; // 전부 옮겨주기

        while(j <= hight) // 두번째 리스트 내 원소가 남아있다면
            mergedNumbers[k++] = numbers[j++]; // 전부 옮겨주기

        for(int l = low; l <= hight; l++) // 병합된 리스트를 원본 리스트에 옮기는 작업
            numbers[l] = mergedNumbers[l];
    }
}
Java
복사