정렬 (Sorting)

Jeonghwan Yoon·2025년 3월 30일

정렬이란?

데이터를 특정 기준(크기, 순서 등)에 따라 정해진 순서로 나열하는 과정
보통 오름차순(작은 → 큰) 또는 내림차순(큰 → 작은) 정렬이 기본
숫자, 문자열, 구조체 등 모든 자료형이 정렬 대상이 될 수 있음

정렬이 중요한 이유

이진 탐색, 중복 제거, 효율적인 자료 처리 등을 위해 먼저 정렬이 선행되어야 함
많은 알고리즘의 전처리 과정에서 필수적으로 사용됨

주요 정렬 알고리즘 비교

알고리즘	시간 복잡도	공간 복잡도	특징
버블 정렬	O(N²)	O(1)	인접한 요소끼리 비교, 가장 단순
선택 정렬	O(N²)	O(1)	가장 작은 값을 선택해 앞으로 이동
삽입 정렬	O(N²), 최선 O(N)	O(1)	거의 정렬된 배열에 효율적
병합 정렬	O(N log N)	O(N)	안정 정렬, 분할 정복
퀵 정렬	평균 O(N log N), 최악 O(N²)	O(log N)	가장 빠른 정렬 중 하나
Timsort (파이썬 기본 정렬)	O(N log N)	O(N)	삽입 + 병합 정렬 기반, 안정 정렬

파이썬 기본 정렬 함수

sorted(iterable): 정렬된 새 리스트 반환
list.sort(): 리스트 자체를 정렬 (in-place)

arr = [5, 2, 9, 1]
print(sorted(arr))  # [1, 2, 5, 9]
arr.sort()
print(arr)          # [1, 2, 5, 9]

옵션: key=, reverse=

words = ["apple", "banana", "cat"]
words.sort(key=len, reverse=True)  # 길이 기준 내림차순
print(words)  # ['banana', 'apple', 'cat']

직접 구현 예시 (3종)

버블 정렬

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

선택 정렬

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

삽입 정렬

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

정렬 알고리즘 선택 기준

상황	추천 알고리즘
거의 정렬된 배열	삽입 정렬
간단한 구조 구현	선택, 버블
빠른 정렬 필요	퀵 정렬
안정 정렬 필요	병합 정렬, Timsort
파이썬 사용	`sort()`, `sorted()`