수 정렬하기 2

import sys


def main():
    input = sys.stdin.readline

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

    arr.sort()

    for i in arr:
        print(i)


main()

Python의 내장 정렬 함수를 이용하여 풀면 됩니다.

최악 시간 복잡도가 $O(n \log n)$인 정렬 알고리즘

비교 기반 정렬은 평균 및 최악 시간 복잡도가 $O(n \log n)$보다 작을 수 없음이 증명되어 있습니다. 아래 세 가지 정렬 알고리즘이 그러한 알고리즘 중 일부입니다.

아직 이해하기 어렵다면 나중에 다시 읽어도 됩니다.

병합 정렬 (Merge Sort)

def merge_sort(A: list[T]) -> list[T]:
    return merge_sort_impl(A, 0, len(A) - 1)

def merge_sort_impl(A: list[T], left: int, right: int) -> list[T]:
    if left == right:
        return [A[left]]

    mid = (left + right) // 2
    left_arr = merge_sort_impl(A, left, mid)
    right_arr = merge_sort_impl(A, mid + 1, right)

    return merge(left_arr, right_arr)

def merge(left: list[T], right: list[T]) -> list[T]:
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while i < len(left):
        result.append(left[i])
        i += 1

    while j < len(right):
        result.append(right[j])
        j += 1

    return result

병합 정렬(merge sort)은 분할 정복의 대표적인 예시로, 배열을 반으로 나누는 과정을 반복하여 크기를 1로 만든 후, 두 배열을 합치면서 정렬된 상태를 유지하여 최종적으로 정렬된 배열을 얻는 알고리즘입니다.

힙 정렬 (Heap Sort)

from heapq import heappop, heappush

def heap_sort(A: list[T]) -> list[T]:
    heap = []
    for x in A:
        heappush(heap, x)

    result = []
    while heap:
        result.append(heappop(heap))

    return result

힙 정렬(heap sort)은 힙(heap)이라고 불리는 자료구조를 사용하여 정렬하는 알고리즘입니다. 힙은 임의의 원소를 삽입하는 연산(heappush)과 최솟값을 추출하는 연산(heappop)을 $O(\log n)$에 수행할 수 있는데, 이를 $n$번 반복하는 것입니다. 지금 다루기에는 약간 복잡한 자료구조라서 나중에 다시 알아보겠습니다.

팀 정렬 (Tim Sort)

팀 정렬(Tim sort)은 파이썬의 내장 정렬 함수, 즉 list.sort와 sorted에서 사용되는 정렬 알고리즘입니다. 시간 복잡도, 메모리 복잡도, 안정성 모두 정렬 알고리즘들 중 좋은 편에 속하기 때문에, 문제를 풀 때는 다른 알고리즘을 직접 구현할 필요없이 내장 함수를 사용하면 됩니다.