문제

BOJ 27551, 수 정렬하기 2

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 내장 sort함수를 이용할 수도 있으나, 머지소트를 구현해서 사용해 본다. 평균적으로 quicksort더 빠르지만, 직접 구현한 quicksort를 사용하지 않는 이유는 맨 처음 원소를 피봇으로 고르는 과정에서 특정 자료에 대해 정렬을 $O(N^2)$에 수행할 수 있기 때문이다. (거의 정렬이 되어 있고, 매번 pivot을 맨 앞에서 골라 n번을 비교하는 경우)

개선

코드

시간복잡도

• $O(N\times log_2N)$

C++

#include <iostream>
using namespace std;

int a[1'000'004];
int tmp[1'000'004];

void merge(int st, int en) {
	int mid = (st + en) / 2;
	int l = st, r = mid;
	for (int i = st; i < en; ++i) {
		if (l == mid)
			tmp[i] = a[r++];
		else if (r == en)
			tmp[i] = a[l++];
		else if (a[l] < a[r])
			tmp[i] = a[l++];
		else
			tmp[i] = a[r++];
	}
	for (int i = st; i < en; ++i)
		a[i] = tmp[i];
}

void mergeSort(int st, int en) {
	if (en - st <= 1)
		return ;
	int mid = (st + en) / 2;
	mergeSort(st, mid);
	mergeSort(mid, en);
	merge(st, en);
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	mergeSort(0, n);
	for (int i = 0; i < n; ++i)
		cout << a[i] << ' ';
}

Java

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

public class J2751_수정렬하기2 {
    static ArrayList<Integer> tmp = new ArrayList<>(1_000_000);
    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());
        ArrayList<Integer> a = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            a.add(Integer.parseInt(br.readLine()));
            tmp.add(0);
        }
        mergeSort(a, 0, n);
        for (int i = 0; i < n; i++)
            bw.write(a.get(i) + " ");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void mergeSort(ArrayList<Integer> a, int st, int en) {
        if (en - st <= 1)
            return ;
        int mid = (st + en) / 2;
        mergeSort(a, st, mid);
        mergeSort(a, mid, en);
        merge(a, st, en);
    }

    private static void merge(ArrayList<Integer> a, int st, int en) {
        int mid = (st + en) / 2;
        int l = st, r = mid;
        for (int i = st; i < en; i++) {
            if (l == mid)
                tmp.set(i, a.get(r++));
            else if (r == en)
                tmp.set(i, a.get(l++));
            else if (a.get(l) < a.get(r))
                tmp.set(i, a.get(l++));
            else
                tmp.set(i, a.get(r++));
        }
        for (int i = st; i < en; i++)
            a.set(i, tmp.get(i));
    }
}