라이브러리 정렬
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
라이브러리 정렬은 삽입 정렬과 유사하지만, 배열에 빈 공간을 추가하여 삽입 속도를 향상시킨 정렬 알고리즘이다. 이 알고리즘은 이진 탐색, 삽입, 재조정의 세 단계를 거치며, log n 번의 라운드로 작동한다. 삽입 과정에서 빈 공간을 활용하여 요소 이동을 최소화하고, 재균형 과정을 통해 배열 전체에 빈 공간을 균등하게 분산시킨다.
(내용 없음)
```
2. 구현
2. 1. 알고리즘
n개의 요소를 가진 배열이 주어졌을 때, 특정 비율(ε)만큼의 빈 공간을 추가하여 최종 배열의 크기를 ''(1 + ε)n''으로 만든다. 라이브러리 정렬 알고리즘은 대략 ''log n'' 번의 라운드로 작동한다. 각 라운드에서는 이전 라운드까지 삽입된 요소의 수만큼 새로운 요소를 배열에 삽입한 후, 배열 전체의 균형을 맞추는 재균형(조정) 단계를 거친다.
알고리즘의 핵심적인 세 단계는 다음과 같다.
1. 이진 탐색: 이미 정렬되어 삽입된 요소들 내에서 이진 탐색을 적용하여 새로 삽입할 요소의 정확한 위치를 찾는다. 탐색 과정에서 중간 지점이 빈 공간일 경우, 좌우로 선형적으로 이동하여 실제 데이터가 있는 위치를 기준으로 탐색을 계속한다.
2. 삽입: 이진 탐색으로 찾은 위치에 새로운 요소를 삽입한다. 삽입된 요소 뒤의 요소들은 다음 빈 공간이 나올 때까지 한 칸씩 뒤로 밀려나게 된다. 이 과정은 높은 확률로 로그 시간 안에 수행된다.
3. 재균형 (조정): 배열 내의 각 요소 쌍 사이에 빈 공간을 균등하게 재분배하여 이후 삽입을 위한 공간을 확보한다. 각 라운드에서 수행되는 재균형 작업 자체는 해당 시점의 배열 크기에 비례하는 선형 시간이 소요된다. 이 작업이 ''log n'' 번의 라운드에 걸쳐 반복되므로, 알고리즘 전체에서 재균형에 소요되는 총 시간 복잡도는 O(''n'' log ''n'')이 된다.
2. 2. 의사 코드
라이브러리 정렬의 핵심 연산은 배열 요소 사이에 간격을 만들어 재배열하는 재균형(rebalance)과 이를 이용해 정렬을 수행하는 정렬(sort) 함수이다.
다음은 재균형 함수의 의사 코드이다. 이 함수는 배열 `A`의 `begin`부터 `end`까지의 요소를 가져와 각 요소 뒤에 빈 간격(gap)을 하나씩 추가하여 배열 크기를 두 배로 늘린다.
```wiki
'''절차''' 재균형(A, 시작, 끝)
r ← 끝
w ← 끝 × 2 // 쓰기 포인터는 읽기 포인터의 두 배 위치에서 시작
'''while''' r ≥ 시작 '''do'''
A[w] ← A[r] // 원래 요소를 새 위치로 복사
A[w-1] ← 간격 // 요소 앞에 간격 삽입
r ← r − 1 // 읽기 포인터 이동
w ← w − 2 // 쓰기 포인터 이동 (요소 + 간격만큼)
```
다음은 정렬 함수의 의사 코드이다.
```wiki
'''절차''' 정렬(A)
n ← 길이(A)
S ← n개의 간격으로 구성된 새 배열 // 최종 정렬될 배열 S 생성
'''for''' i ← 1 to floor(log2(n-1)) '''do''' // 총 log n 번의 라운드 수행
// 라운드 시작 전, 이전 라운드에서 삽입된 요소들 사이에 간격을 넣어 재균형
재균형(S, 1, 2^(i-1))
// 현재 라운드에서 삽입할 요소들을 처리 (이전 라운드 요소 수만큼)
'''for''' j ← 2^(i-1) to 2^i '''do'''
// 삽입할 요소 A[j]의 위치를 배열 S의 앞 2^i개 공간 내에서 찾음
ins ← 이진탐색(A[j], S, 2^i)
// 찾은 위치 ins에 A[j] 삽입 (필요시 뒤 요소들을 밀어냄)
A[j]를 S[ins]에 삽입
```
여기서 `이진탐색(el, A, k)` 함수는 특별한 방식으로 동작한다. 이 함수는 배열 `A`의 처음 `k`개 공간(요소와 간격 포함) 내에서 요소 `el`이 들어갈 위치를 찾기 위해 이진 탐색을 수행한다. 탐색 과정에서 빈 간격은 건너뛰고 요소가 있는 위치만 비교 대상으로 삼는다. 요소를 삽입할 때는, 만약 동일한 값을 가진 요소가 이미 존재한다면 그 뒤의 빈 간격을 우선적으로 고려하여 삽입 위치를 결정한다. 즉, 채워진 요소보다는 빈 간격을 선호하여 삽입한다.
알고리즘의 주요 단계는 다음과 같다.
# '''이진 탐색''': 이미 정렬되어 배열 `S`에 삽입된 요소들을 대상으로 이진 탐색을 수행하여 새로운 요소 `A[j]`가 삽입될 위치 `ins`를 찾는다. 탐색 중 빈 간격을 만나면 건너뛴다.
# '''삽입''': 찾은 위치 `ins`에 요소 `A[j]`를 삽입한다. 만약 해당 위치에 이미 다른 요소가 있다면, 빈 간격이 나올 때까지 뒤따르는 요소들을 한 칸씩 뒤로 밀어낸다.
# '''재균형''': 각 라운드가 시작될 때, 이전 라운드까지 삽입된 요소들 사이에 빈 간격을 추가하여 배열 `S`를 재구성한다. 이 작업은 해당 라운드 시작 시점에 `S`에 들어있는 요소 수에 비례하는 시간이 걸린다. 라운드마다 처리하는 요소 수가 두 배씩 증가하므로, 전체 재균형 작업에 드는 총 시간은 선형 시간 복잡도인 O(n)에 가깝다.
참조
[1]
논문
Insertion Sort is O(n log n)
2004-07-01
[2]
간행물
Insertion Sort is O(n log n)
http://csis.pace.edu[...]
2006-06
[3]
url
https://arxiv.org/ab[...]
[4]
간행물
Insertion Sort is O(n log n)
[5]
논문
Insertion Sort is O(n log n)
2004-07-01
[6]
간행물
Insertion Sort is O(n log n)
http://csis.pace.edu[...]
2019-11-20
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com