요약
이 강의에서는 정렬 알고리즘에 대해 다루며, 특히 비교 모델에서의 정렬 하한과 직접 접근 배열 및 해시 테이블을 사용한 선형 시간 정렬 방법을 설명합니다. 주요 내용은 다음과 같습니다.
- 비교 모델에서 n log n보다 빠른 정렬은 불가능합니다.
- 직접 접근 배열을 사용하여 특정 조건에서 선형 시간 정렬이 가능합니다.
- 계수 정렬과 기수 정렬을 통해 더 넓은 범위의 입력에 대해 효율적인 정렬을 수행할 수 있습니다.
강의 소개
강의 소개 및 지난 강의 요약. 지난 강의에서는 검색 문제를 다루며, 특정 계산 모델에서 log n 시간보다 빠르게 검색할 수 없음을 보였습니다. 하지만 랜덤 접근이 가능한 모델에서는 직접 접근 배열을 사용하여 상수 시간에 검색할 수 있습니다. 직접 접근 배열은 키를 인덱스로 사용하여 배열에 저장하는 방식으로, 공간 복잡도 문제를 해결하기 위해 해시 함수와 해시 테이블을 사용했습니다. 해시 테이블은 기대 시간에는 상수 시간으로 검색, 삽입, 삭제가 가능하지만, 최악의 경우에는 선형 시간이 걸릴 수 있습니다.
비교 모델에서의 정렬 하한
비교 모델에서 정렬 알고리즘의 하한은 n log n입니다. 이는 결정 트리를 사용하여 증명할 수 있으며, 정렬 알고리즘의 가능한 출력 수는 n!입니다. 결정 트리의 높이는 적어도 log(n!)이어야 하며, 이는 n log n으로 근사할 수 있습니다. 따라서 비교 모델에서는 n log n보다 빠른 정렬이 불가능합니다.
직접 접근 배열 정렬
직접 접근 배열을 사용하여 더 빠르게 정렬하는 방법을 설명합니다. 키가 고유하고 작은 범위 내에 있다고 가정하면, 직접 접근 배열을 생성하고 각 항목을 해당 키에 해당하는 인덱스에 저장할 수 있습니다. 그런 다음 배열을 순회하면서 항목을 순서대로 반환하면 정렬된 결과를 얻을 수 있습니다. 이 알고리즘은 O(n + u) 시간이 걸리며, u가 n에 비례하면 선형 시간 정렬이 가능합니다.
튜플 정렬
키 범위가 더 넓은 경우(예: u ≤ n^2) 튜플 정렬을 사용하여 정렬할 수 있습니다. 각 키를 두 개의 작은 숫자로 분해하고, 가장 중요하지 않은 숫자부터 시작하여 안정적인 정렬 알고리즘을 사용하여 정렬합니다. 안정적인 정렬 알고리즘은 동일한 키를 가진 항목의 상대적인 순서를 유지합니다.
계수 정렬
계수 정렬은 직접 접근 배열을 사용하지만, 각 키에 대해 하나의 항목 대신 체인(연결 리스트 또는 동적 배열)을 저장합니다. 항목을 삽입할 때 순서를 유지하고, 체인을 순회하면서 항목을 순서대로 반환합니다. 계수 정렬은 O(n + u) 시간이 걸립니다.
기수 정렬
기수 정렬은 정수의 최대 크기 u를 기반으로 숫자를 분해하고 튜플 정렬을 사용하여 정렬합니다. 각 숫자는 0에서 n까지의 범위를 가질 수 있습니다. 숫자의 개수는 log_n(u)입니다. 계수 정렬을 사용하여 숫자를 정렬하고, 가장 중요하지 않은 것부터 가장 중요한 것 순으로 정렬합니다. 기수 정렬의 실행 시간은 n + n * log_n(u)입니다. u가 n^c보다 작으면 기수 정렬은 선형 시간 알고리즘입니다.
