출시·고도화 중
Algorithm
정렬은 데이터를 정해진 순서로 늘어놓는 알고리즘입니다. 병합 · 퀵 · 힙 정렬, 안정성, n log n 하한, 계수 · 기수 정렬, 언어별 내장 정렬을 다룹니다.
정렬(sorting)은 원소들을 크기순, 사전순, 시각순처럼 정해진 순서로 다시 늘어놓는 알고리즘입니다. 두 원소를 비교해 앞뒤를 정하는 비교 정렬(버블 · 삽입 · 선택 · 병합 · 퀵 · 힙 정렬)과, 정수의 값이나 자릿수를 직접 이용하는 계수 정렬 · 기수 정렬 같은 비비교 정렬로 크게 나뉩니다.
정렬은 이진 탐색, 중복 제거, 구간 병합, 순위 계산 같은 수많은 작업의 준비 단계이기 때문에 가장 먼저 배우는 기본 알고리즘으로 꼽힙니다. 비교 정렬은 최악의 경우 Ω(n log n)번보다 적게 비교할 수 없다는 하한, 안정 정렬과 제자리 정렬의 차이, Python의 Timsort나 대부분의 C++ std::sort 구현이 쓰는 인트로소트 같은 내장 정렬의 동작을 알면 실무와 코딩 테스트에서 올바른 선택을 할 수 있습니다.
공부할 때는 작은 배열을 손으로 따라가며 삽입 · 병합 · 퀵 정렬의 동작을 익힌 다음, 병합 정렬과 퀵 정렬을 직접 구현하고 최선 · 평균 · 최악 복잡도를 비교해 보는 것이 좋습니다. 이후에는 key 함수와 비교 함수로 내장 정렬을 다루는 법을 익히고, 구간 병합이나 역순 쌍 세기처럼 정렬을 응용한 문제를 연습하면 됩니다.
병합 정렬은 반으로 나누어 합치고, 퀵 정렬은 기준값으로 가릅니다. 두 방식 모두 평균 O(n log n)에 동작합니다.
안정 정렬은 같은 키를 가진 원소의 원래 순서를 지키고, 제자리 정렬은 추가 메모리를 거의 쓰지 않습니다. 어느 쪽이 중요한지는 용도에 따라 달라집니다.
결정 트리 논증에 따르면 비교만으로 정렬하는 알고리즘은 최악의 경우 n log n에 비례하는 비교가 필요합니다. 병합 정렬과 힙 정렬은 이 하한에 도달합니다.
계수 정렬과 기수 정렬은 값의 범위나 자릿수가 제한된 정수를 원소끼리 비교하지 않고 거의 선형 시간에 정렬합니다.
merge_sort는 목록을 반으로 나누어 각각 재귀로 정렬한 뒤, 두 정렬된 목록의 맨 앞을 비교해 작은 쪽부터 꺼내며 하나로 합칩니다. 값이 같을 때 왼쪽을 먼저 꺼내므로(<=) 안정 정렬이 되고, 입력과 상관없이 O(n log n)에 동작합니다. 마지막 줄은 결과가 내장 함수 sorted()와 같은지 확인합니다.
merge_sort.py
def merge_sort(items):
"""Return a new sorted list (stable, O(n log n))."""
if len(items) <= 1:
return list(items)
mid = len(items) // 2
left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # take the left one on ties: stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort(data) == sorted(data)) # True
python merge_sort.py정렬 에 관해 묻고, 경험을 나누고, 의견을 주고받는 곳입니다.
아직 토론이 없습니다. 첫 이야기를 시작해 보세요.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.
첫 댓글을 남겨 보세요.