BOJ 2751 수 정렬하기 2

1 개요

BOJ 2751 수 정렬하기 2

• 백준 온라인 저지 2751번 문제
• BOJ 13단계

• 병합정렬(Merge Sort) 혹은 힙 정렬(Heap Sort)을 사용해 봅니다
• 알고리즘 분류: 정렬

2 C++

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    int arr[1000000];
    for(int i=0; i<N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+N);
    for(int i=0; i<N; i++) {
        cout << arr[i] << '\n';    
    }
}

3 Java

병합정렬

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
public class Main {
	private static void merge(int arr[], int left, int middle, int right) {
		int n1 = middle - left + 1;
		int n2 = right - middle;
		int L[] = new int[n1];
		int R[] = new int[n2];
		int i, j, k;
		for(i=0; i<n1; ++i) L[i]=arr[left+i];
		for(j=0; j<n2; ++j) R[j]=arr[middle+j+1];
		i=0; j=0; k=left;
		while( i<n1 && j<n2) {
			if(L[i] <= R[j]) { arr[k] = L[i]; i++; }
			else { arr[k] = R[j]; j++; }
			k++;
		}
		while( i < n1 ) { arr[k] = L[i]; i++; k++; }
		while( j < n2 ) { arr[k] = R[j]; j++; k++; }
	}
	private static void merge_sort(int arr[], int left, int right) {
		if(left >= right) return;
		int middle = (left+right)/2;
		merge_sort(arr, left, middle);
		merge_sort(arr, middle+1, right);
		merge(arr, left, middle, right);
	}
	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());
		int arr[] = new int[n];
		for(int i=0; i<n; i++) arr[i] = Integer.parseInt(br.readLine());
		merge_sort(arr, 0, n-1);
		for(int i=0; i<n; i++) bw.write( arr[i] + "\n" );
		bw.flush();
	}
}

4 PHP

내장함수(퀵소트) 사용

<?php
fscanf(STDIN,'%d',$n);
$nums = [];
for($i=0; $i<$n; $i++) $nums[] = intval(fgets(STDIN));
sort( $nums );
ob_start();
foreach($nums as $num) echo $num . "\n";
ob_flush();

5 Python

합병정렬 (시간초과)

def merge(arr, left, middle, right):
    n1 = middle - left + 1
    n2 = right - middle
    L = [0] * (n1)
    R = [0] * (n2)
    for i in range(0 , n1):
        L[i] = arr[left + i]
    for j in range(0 , n2):
        R[j] = arr[middle + 1 + j]
    i = j = 0
    k = left
    while i < n1 and j < n2 :
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
def merge_sort(arr, left=0, right=-1):
    if right == -1:
        right = len(arr)-1
    if left < right:
        middle = int((left+(right-1))/2)
        merge_sort(arr, left, middle)
        merge_sort(arr, middle+1, right)
        merge(arr, left, middle, right)
n = int(input())
a = [int(input()) for i in range(n)]
merge_sort( a )
[print( ele ) for ele in a]