kimerikal

수 정렬하기

import sys


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

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

    arr.sort()

    print("\n".join(map(str, arr)))


main()

정렬

정렬(sorting)은 기존 원소들을 재배치하여 증가 또는 감소하는 순서대로 나열하는 것입니다. 다음은 정수들을 작은 수부터 나열하는 오름차순(ascending order) 정렬과 큰 수부터 나열하는 내림차순(descending order) 정렬의 예시입니다.

$$ \begin{align*} [3, 1, 4, 1, 5] \; &\xrightarrow{\text{오름차순}} \; [1, 1, 3, 4, 5] \\ [3, 1, 4, 1, 5] \; &\xrightarrow{\text{내림차순}} \; [5, 4, 3, 1, 1] \end{align*} $$

물론 정수뿐만 아니라 실수, 문자열 등 다양한 자료형을 정렬할 수 있습니다.

정렬은 그 자체로 데이터를 정리해서 보거나 데이터를 정규화하는데 사용할 수 있고, 통계적 특성을 파악하는 데 쓸 수 있습니다. 또한, 정렬된 배열의 다양한 성질을 활용하기 위해 복잡한 알고리즘들은 중간 과정으로 정렬을 포함한 경우가 많습니다.

정렬 알고리즘 분석

다른 알고리즘 분석과 마찬가지로, 정렬 알고리즘도 시간 복잡도(특히 PS의 특성상 최악 시간 복잡도)와 메모리 복잡도를 고려해야합니다. 여기에 더해, 정렬 알고리즘은 안정성(stability)도 중요합니다.

  • 최악 시간 복잡도
    비교 연산을 기반으로 하는 정렬 알고리즘의 평균 및 최악 시간 복잡도는 $O(n \log n)$이 최선임이 알려져 있습니다. 단순한 알고리즘이나 잘못 구현한 경우에 드는 $O(n^2)$ 알고리즘은 대개 문제 풀이에 부적합합니다.
  • 메모리 복잡도
    정렬 과정에서 기존 배열 외에 추가로 사용하는 메모리는 $O(n)$이면 되는데, 이 조건은 웬만하면 만족합니다.
  • 안정성
    배열의 원소는 정렬의 기준이 되는 값인 키(key)외에 추가적인 정보인 위성 데이터(satellite data)를 가질 수 있습니다. 정렬을 수행하고 나서 키가 같은 원소들 사이에서 위성 데이터의 순서가 기존 배열에서의 순서와 같음이 보장된다면, 정렬 알고리즘이 안정적(stable)이라고 합니다. 같은 배열에서 키를 다르게 하며 여러 번 정렬을 수행할 때, 안정적인 정렬 알고리즘은 이전 정렬의 결과를 보존하므로 유용합니다.

비교기반 정렬의 평균 시간 복잡도의 $O(n \log n)$ 하한은 나중에 증명하겠습니다.

Python에서 정렬하기

Python에서 정렬은 두 가지 방법으로 할 수 있습니다.

  • sorted 함수
    리스트를 포함한 모든 이터러블을 정렬할 수 있습니다. 새로 정렬된 리스트를 만들어 반환합니다.
  • list.sort 메소드
    list자료형을 정렬할 때 사용합니다. 이 메소드는 리스트를 제자리에서 정렬하므로 원본 리스트가 변경됩니다. 추가 메모리 할당이 적게 들어 조금 더 빠릅니다.

예를 들어, 위 코드에서 arr = sorted(int(input()) for _ in range(n))으로 작성하면 입력 받기와 정렬을 한 줄로 처리할 수도 있습니다.

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

앞서 말했듯 정렬 알고리즘은 쓰임새가 많기 때문에 최악 시간 복잡도가 $O(n \log n)$인 내장 함수를 제공하지 않는 프로그래밍 언어가 거의 없습니다. 그러나 컴퓨터 과학에서 정렬 알고리즘의 의미가 크고, 알고리즘과 그 방법론을 분석하는데 중요하기 때문에 간단하게나마 짚고 넘어가겠습니다.

아래 네 가지 정렬 알고리즘은 모두 최악 시간 복잡도가 $O(n^2)$입니다. 대입, 인덱싱 등 기본 연산들이 잘 드러나도록 의도적으로 Python답지 않게 구현했습니다.

삽입 정렬

def insertion_sort(A: list[T]) -> None:
    for i in range(1, len(A)):
        key = A[i]
        for j in range(i - 1, -1, -1):
            if A[j] > key:
                A[j + 1] = A[j]
            else:
                break
        A[j + 1] = key

삽입 정렬(insertion sort)은 i를 기준으로 왼쪽 A[:i] 부분 배열을 정렬된 상태로 유지하면서 새롭게 추가할 A[i]가 올바른 위치에 들어갈 때 까지 이전 원소와 비교하여 바꿔나갑니다. 원소가 하나인 배열 [A[0]]은 이미 정렬된 상태이므로, i를 $1$부터 시작합니다.

선택 정렬

def selection_sort(A: list[T]) -> None:
    for i in range(len(A)):
        min_idx = i
        for j in range(i + 1, len(A)):
            if A[j] < A[min_idx]:
                min_idx = j
        A[i], A[min_idx] = A[min_idx], A[i]

선택 정렬(selection sort)은 i를 기준으로 오른쪽 A[i:] 부분 배열에서 가장 작은 원소를 찾아 A[i]와 교환해 나갑니다. 삽입 정렬과 마찬가지로 A[i:] 부분 배열이 정렬된 상태가 유지됩니다.

거품 정렬

def bubble_sort(A: list[T]) -> None:
    for i in range(len(A)):
        for j in range(len(A) - 1, i, -1):
            if A[j] < A[j - 1]:
                A[j], A[j - 1] = A[j - 1], A[j]

거품 정렬(bubble sort)은 인접한 두 원소를 비교하여 큰 원소를 오른쪽으로 이동시키는 방식으로 정렬합니다. 배열에서 뒤 쪽 i개의 원소가 정렬된 상태를 유지합니다.

퀵 정렬

def quick_sort(A: list[T]) -> None:
    quick_sort_impl(A, 0, len(A) - 1)


def quick_sort_impl(A: list[T], start: int, end: int) -> None:
    if start < end:
        pivot = partition(A, start, end)
        quick_sort_impl(A, start, pivot - 1)
        quick_sort_impl(A, pivot + 1, end)


def partition(A: list[T], start: int, end: int) -> int:
    pivot = A[end]
    i = start - 1
    for j in range(start, end):
        if A[j] < pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[end] = A[end], A[i + 1]
    return i + 1

퀵 정렬(quick sort)은 분할 정복(divide and conquer) 방법을 사용하여 배열을 정렬합니다. 일반적인 경우 좋은 성능을 보이지만, 최악의 경우에 $O(n^2)$까지 느려질 수 있으므로 대부분의 문제에서 사용할 수 없습니다.

댓글