[python] 백준 > 정렬 > 수 정렬하기2(2751)

[문제]

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

입력

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

출력

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

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

[풀이-시간초과(버블정렬)]

import sys
input = sys.stdin.readline

N = int(input())
arr = [int(input()) for _ in range(N)]

def bubbleSort(x):
    for size in reversed(range(len(x))):
        for i in range(size):
            if x[i] > x[i+1]:
                swap(x, i, i+1)
    
    for j in x:
        print(j)

def swap(x, i, j):
    x[i], x[j] = x[j], x[i]

bubbleSort(arr)

[풀이-성공(병합정렬)]

import sys
input = sys.stdin.readline

N = int(input())
arr = [int(input()) for _ in range(N)]

def mergeSort(array):
    if len(array) <= 1:
        return array
    mid = len(array)//2
    left = mergeSort(array[:mid])
    right = mergeSort(array[mid:])

    i, j, k = 0, 0, 0

    while i<len(left) and j<len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i+=1
        else:
            array[k] = right[j]
            j+=1
        k+=1
    
    if i==len(left):
        while j<len(right):
            array[k] = right[j]
            j+=1
            k+=1
    elif j==len(right):
        while i<len(left):
            array[k] = left[i]
            i+=1
            k+=1
    return array

answer = mergeSort(arr)
for i in answer:
    print(i)

[느낀점]

• 항상 내장함수인 sorted나 sort만 써서 정렬 알고리즘의 기초에 대해 까먹고 있었다.
• 이번 기회에 병합 정렬 알고리즘에 대해 다시 알게되어 좋았다.
• 퀵정렬과 병합정렬이 시간이 가장 적게 걸린다.
• 그러나 퀵정렬의 경우 순서가 완전 다르게 돼있으면 시간이 오래걸린다.
• 병합정렬은 항상 nlogn이 걸리기 때문에 안전하다