[자료구조] 내부 정렬 Internal Sorting
정렬 (Sorting)
정의
- n개의 요소를 오름차순으로 재배열하는 것
- 입력: 7, 3, 6, 2, 1
- 정렬 후 출력: 1, 2, 3, 6, 7
정렬 방법
- 내부 정렬 (Internal Sorting)
- PQ 기반 정렬 (PQ based sorting)
- 선택 정렬 (Selection sort)
- 삽입 정렬 (Insertion sort)
- 힙 정렬 (Heap sort)
- 외부 정렬 (External Sorting)
Priority Queue(PQ)
정의
- 우선 순위가 부여된 요소들을 저장하는 추상 데이터 타입으로, 임의의 요소 삽입을 지원하지만 요소 제거는 우선 순위에 따라 이루어진다.
특징
- 스택, 큐, 리스트, 트리와 같은 위치 기반 데이터 구조와 근본적으로 다름.
- 기존의 데이터 구조는 요소를 특정 위치에 저장하며, 이는 삽입 및 삭제 방법에 의해 결정됨
- 우선 순위 큐 ADT는 요소들을 그들의 우선 순위에 따라 저장하며, 사용자에게 "위치" 개념을 노출하지 않는다.
- 우선 순위 큐에서는 우선 순위가 가장 높은 요소가 언제든지 제거될 수 있다.
Sorting with a Priority Queue
우선 순위 큐를 사용하여 비교 가능한 요소 집합을 정렬할 수 있다.
- 삽입 연산을 통해 요소들을 하나씩 삽입
removeMin연산을 통해 요소들을 정렬된 순서로 제거한다.
Algorithm PQ-Sort(S, C)
Input sequence S, comparator C for
the elements of S
Output sequence S sorted in
increasing order according to C
P <- priority queue with
comparator C
while S.isEmpty ()
e <- S.removeFirst ()
P.insert (e, ⊘)
while P.isEmpty()
e <- P.removeMin().getKey()
S.addLast(e)우선 순위 큐(PQ)의 구현
PQ 구현 방법
- 시퀀스를 이용한 PQ
- 단순하지만 효율적이지 않음
- 두 가지 정렬 알고리즘 사용
- 선택 정렬 (Selection sort)
- 삽입 정렬 (Insertion sort)
- 힙을 기반으로 한 PQ
- 효율적인 구현
- O(log n) 시간 내에 PQ 연산을 지원
- 힙 정렬 (Heap-sort) 사용
시퀀스를 기반으로 한 우선 순위 큐
정렬되지 않은 리스트로 구현
성능:
insert: O(1)- 항목을 시퀀스의 시작이나 끝에 삽입할 수 있기 때문
removeMin,min: O(n)- 가장 작은 키를 찾기 위해 전체 시퀀스를 탐색해야 하기 때문
정렬된 리스트로 구현
성능:
insert: O(n)- 항목을 삽입할 위치를 찾아야 하기 때문
removeMinmin: O(1)- 가장 작은 키가 항상 리스트의 시작에 있기 때문
Selection-Sort
정의:
- 선택 정렬은 우선 순위 큐가 정렬되지 않은 시퀀스로 구현된 PQ-정렬의 변형
선택 정렬의 실행 시간:
- n개의 삽입 연산으로 우선 순위 큐에 요소를 삽입하는데 O(n) 시간이 소요
- n개의
removeMin연산으로 우선 순위 큐에서 정렬된 순서로 요소를 제거하는데 걸리는 시간:
$O(1+2+⋯+(n−1)+n)=O(i=1∑ni)
O(1+2+⋯+(n−1)+n)=O(∑i=1ni)O(1 + 2 + \cdots + (n - 1) + n) = O\left(\sum_{i=1}^{n} i\right)$
결론:
- O(n^2) 시간이 소요
Selection-Sort 예시
입력:(7,4,8,2,5,3,9)(7, 4, 8, 2, 5, 3, 9)(7,4,8,2,5,3,9)
Phase 1: 삽입 연산
- 시퀀스 S에서 우선 순위 큐 P로 요소를 하나씩 삽입
| 단계 | Sequence S | Priority Queue P |
|---|---|---|
| (a) | (4, 8, 2, 5, 3, 9) | (7) |
| (b) | (8, 2, 5, 3, 9) | (7, 4) |
| (c) | (2, 5, 3, 9) | (7, 4, 8) |
| (d) | (5, 3, 9) | (7, 4, 8, 2) |
| (e) | (3, 9) | (7, 4, 8, 2, 5) |
| (f) | (9) | (7, 4, 8, 2, 5, 3) |
| (g) | () | (7, 4, 8, 2, 5, 3, 9) |
Phase 2: 제거 연산
- 우선 순위 큐 P에서 요소를 제거하여 정렬된 순서로 시퀀스 S에 삽입
| 단계 | Sequence S | Priority Queue P |
|---|---|---|
| (a) | (2) | (7, 4, 8, 5, 3, 9) |
| (b) | (2, 3) | (7, 4, 8, 5, 9) |
| (c) | (2, 3, 4) | (7, 8, 5, 9) |
| (d) | (2, 3, 4, 5) | (7, 8, 9) |
| (e) | (2, 3, 4, 5, 7) | (8, 9) |
| (f) | (2, 3, 4, 5, 7, 8) | (9) |
| (g) | (2, 3, 4, 5, 7, 8, 9) | () |
Phase 1 : 요소들을 순차적으로 우선 순위 큐에 삽입
Phase 2 : 요소들을 정렬된 순서로 제거하여 최종적으로 정렬된 시퀀스
Insertion-Sort
정의:
- 삽입 정렬은 우선 순위 큐가 정렬된 시퀀스로 구현된 PQ-정렬의 변형
삽입 정렬의 실행 시간:
- n개의 삽입 연산으로 우선 순위 큐에 요소를 삽입하는데 걸리는 시간:
$O(1+2+⋯+(n−1)+n)=O(i=1∑ni)
O(1+2+⋯+(n−1)+n)=O(∑i=1ni)O(1 + 2 + \cdots + (n - 1) + n) = O\left(\sum_{i=1}^{n} i\right)$
- n개의
removeMin연산으로 우선 순위 큐에서 정렬된 순서로 요소를 제거하는데 O(n) 시간이 소요.
결론:
- O(n^2) 시간이 소요.
Insertion-Sort 예시
Phase 1: 삽입 연산
- 시퀀스 S에서 우선 순위 큐 P로 요소를 하나씩 삽입
| 단계 | Sequence S | Priority Queue P |
|---|---|---|
| (a) | (4, 8, 2, 5, 3, 9) | (7) |
| (b) | (8, 2, 5, 3, 9) | (4, 7) |
| (c) | (2, 5, 3, 9) | (4, 7, 8) |
| (d) | (5, 3, 9) | (2, 4, 7, 8) |
| (e) | (3, 9) | (2, 4, 5, 7, 8) |
| (f) | (9) | (2, 3, 4, 5, 7, 8) |
| (g) | () | (2, 3, 4, 5, 7, 8, 9) |
Phase 2: 제거 연산
- 우선 순위 큐 P에서 요소를 제거하여 정렬된 순서로 시퀀스 S에 삽입
| 단계 | Sequence S | Priority Queue P |
|---|---|---|
| (a) | (2) | (3, 4, 5, 7, 8, 9) |
| (b) | (2, 3) | (4, 5, 7, 8, 9) |
| (c) | (2, 3, 4) | (5, 7, 8, 9) |
| (d) | (2, 3, 4, 5) | (7, 8, 9) |
| (e) | (2, 3, 4, 5, 7) | (8, 9) |
| (f) | (2, 3, 4, 5, 7, 8) | (9) |
| (g) | (2, 3, 4, 5, 7, 8, 9) | () |
Phase 1 : 요소들을 순차적으로 우선 순위 큐에 삽입
Phase 2 : 요소들을 정렬된 순서로 제거하여 최종적으로 정렬된 시퀀스
In-Place Selection-Sort 및 Insertion-Sort
외부 데이터 구조를 사용하지 않고, 선택 정렬과 삽입 정렬을 제자리에서 구현할 수 있습니다. 입력 시퀀스의 일부가 우선 순위 큐로 사용.
In-Place Insertion-Sort
- 시퀀스의 초기 부분을 정렬된 상태로 유지
- 시퀀스를 수정하는 대신, 교환(swap)을 사용
Quick-Sort
Quick-sort는 분할 정복(divide-and-conquer) 패러다임에 기반한 랜덤화된 정렬 알고리즘
- 분할 (Divide): 랜덤으로 x(피벗)을 선택하고 S를 다음과 같이 분할.
- L: x보다 작은 요소들
- E: x와 같은 요소들
- G: x보다 큰 요소들
- 재귀 (Recur): L과 G를 각각 정렬.
- 정복 (Conquer): L, E, G를 합친다.
Quick-Sort: Partition
입력 시퀀스를 다음과 같이 분할함:
- 각 요소 y를 순차적으로 S에서 제거함
- y를 피벗 x와 비교하여 L, E, G 중 하나에 삽입함
각 삽입과 제거는 시퀀스의 시작이나 끝에서 일어나므로 O(1) 시간이 걸림
따라서, quick-sort의 분할 단계는 O(n) 시간이 걸림
Algorithm partition(S, p)
Input sequence S, position p of pivot
Output subsequences L, E, G of the
elements of S less than, equal to,
or greater than the pivot, resp.
L, E, G empty sequences
x S.remove(p)
while S.isEmpty()
y S.remove(S.first())
if y < x
L.addLast(y)
else if y = x
E.addLast(y)
else { y > x }
G.addLast(y)
return L, E, GQuick-Sort Tree
Quick-sort의 실행은 이진 트리로 묘사됨
- 각 노드는 quick-sort의 재귀 호출을 나타내며 다음을 저장함:
- 실행 전의 정렬되지 않은 시퀀스와 그 피벗
- 실행 후의 정렬된 시퀀스
- 루트는 초기 호출을 나타냄
- 리프는 크기가 0 또는 1인 부분 시퀀스에 대한 호출을 나타냄
최악의 경우 실행 시간
Quick-sort의 최악의 경우는 피벗이 유일한 최소 또는 최대 요소일 때 발생함
L 또는 G 중 하나의 크기가 n-1이고, 다른 하나의 크기는 0임
실행 시간은 다음의 합에 비례함:
n+(n−1)+...+2+1n+(n−1)+...+2+1n + (n - 1) + ... + 2 + 1
따라서, Quick-sort의 최악의 경우 실행 시간은 O(n^2)임
Expected Running Time
Quick-sort가 크기 s인 시퀀스에 대한 재귀 호출을 고려함
- 좋은 호출 (Good call): L과 G의 크기가 각각 3s/4보다 작은 경우
- 나쁜 호출 (Bad call): L과 G 중 하나의 크기가 3s/4보다 큰 경우
호출이 좋은 경우의 확률은 1/2임
- 가능한 피벗의 절반이 좋은 호출을 유발함
In-Place Quick-Sort
Quick-sort는 제자리(in-place)에서 실행되도록 구현할 수 있음
Partition 단계
- 입력 시퀀스의 요소들을 다음과 같이 재배열하기 위해 교체 연산을 사용함
- 피벗보다 작은 요소들은 h보다 작은 순위를 가짐
- 피벗과 같은 요소들은 h와 k 사이의 순위를 가짐
- 피벗보다 큰 요소들은 k보다 큰 순위를 가짐
재귀 호출
- h보다 작은 순위를 가진 요소들을 고려함
- k보다 큰 순위를 가진 요소들을 고려함
In-Place Partitioning
Partition을 수행하기 위해 두 개의 인덱스를 사용하여 S를 L과 E ∪ G로 나눔 (유사한 방법으로 E ∪ G를 E와 G로 나눌 수 있음).
절차
- j와 k가 교차할 때까지 반복:
- j를 오른쪽으로 이동하여 x보다 큰 요소를 찾음
- k를 왼쪽으로 이동하여 x보다 작은 요소를 찾음
- 인덱스 j와 k에 있는 요소를 교환
단계 요약
- j를 오른쪽으로 스캔하여 x보다 큰 요소를 찾음.
- k를 왼쪽으로 스캔하여 x보다 작은 요소를 찾음.
- 인덱스 j와 k의 요소를 교환
- j와 k가 교차할 때까지 반복
Summary of Sorting Algorithms
| Algorithm | Time | Notes |
|---|---|---|
| Selection-Sort | O(n2)O(n^2)O(n2) | - in-place - slow (good for small inputs) |
| Insertion-Sort | O(n2)O(n^2)O(n2) | - in-place - slow (good for small inputs) |
| Quick-Sort | O(nlogn)O(n \log n)O(nlogn) expected | - in-place, randomized - fastest (good for large inputs) |
Insight Penetration: Why is Quick-Sort Faster?
Quick-Sort의 속도가 다른 O(nlogn)O(n \log n)O(nlogn) 알고리즘보다 빠른 이유
일반적으로, Quick-Sort는 다른 O(nlogn) 알고리즘보다 실질적으로 훨씬 빠름. 이는 대부분의 아키텍처에서 내부 루프가 효율적으로 구현될 수 있기 때문이며, 대부분의 실제 데이터에서 설계 선택을 통해 O(n2) 시간이 필요한 경우를 최소화할 수 있기 때문임.
O(nlogn)O(n \log n)
O(n2)O(n^2)
또한, Quick-Sort는 메모리 계층 구조를 잘 활용하며, 가상 메모리와 사용 가능한 캐시를 완벽히 활용함. Quick-Sort는 제자리 정렬이 아니고 보조 메모리를 사용하지만, 현대 컴퓨터 아키텍처에 매우 적합함.
Quick-Sort의 내부 루프 효율성
- 대부분의 컴퓨터 아키텍처에서 매우 효율적임.
- 메모리 접근이 국한됨.
- CPU 캐시 히트 비율이 크게 증가할 수 있음.
Insight Penetration
In-Place Sorting
- 추가적인 메모리를 거의 사용하지 않고 정렬을 수행
- 예: 삽입 정렬 (Insertion Sort)
- 입력 데이터와 루프 변수를 저장하기 위해 추가 메모리를 사용
- 퀵 정렬 (Quick Sort)
- 재귀 호출을 위해 추가 메모리(스택)를 사용
- 재귀 호출 횟수는 입력 데이터 크기에 비례하여 일정하지 않음
- 그러나 실질적으로는 재귀 호출에 상대적으로 적은 메모리를 사용하므로 제자리 정렬 알고리즘으로 분류될 수 있음
- 예: 삽입 정렬 (Insertion Sort)
Online Sorting
- 온라인 정렬 알고리즘은 데이터 시퀀스를 한 번에 제공받지 않고 시간 순서대로 제공받은 데이터를 정렬할 수 있음
- 예: 병합 정렬 (Merge Sort)
- 병합 정렬은 대표적인 온라인 정렬 알고리즘
- 예: 병합 정렬 (Merge Sort)
Divide-and-Conquer
Divide-and-conquer는 일반적인 알고리즘 설계 패러다임임:
- Divide: 입력 데이터 S를 두 개의 서로 겹치지 않는 부분 집합 S1과 S2로 나눔
- Recur: S1과 S2와 관련된 하위 문제를 해결
- Conquer: S1과 S2의 해를 결합하여 S에 대한 해를 만듦
재귀의 기본 사례는 크기가 0 또는 1인 하위 문제
Merge-Sort
Merge-sort는 divide-and-conquer 패러다임에 기반한 정렬 알고리즘:
- 힙 정렬과 유사:
- 비교 연산자를 사용
- O(n log n) 실행 시간을 가짐
- 힙 정렬과 다른점:
- 보조 우선 순위 큐를 사용하지 않음
- 데이터를 순차적으로 접근함 (디스크에 있는 데이터를 정렬하는 데 적합함)
Merge-Sort
Merge-sort는 n개의 요소를 가진 입력 시퀀스 S에 대해 다음 세 가지 단계로 구성됨:
- Divide: S를 대략 n/2개의 요소를 가진 두 개의 시퀀스 S1과 S2로 분할함
- Recur: S1과 S2를 재귀적으로 정렬함
- Conquer: S1과 S2를 하나의 정렬된 시퀀스로 병합함
Algorithm mergeSort(S, C)
Input sequence S with n
elements, comparator C
Output sequence S sorted
according to C
if S.size() > 1
(S1, S2) <- partition(S, n/2)
mergeSort(S1, C)
mergeSort(S2, C)
S <- merge(S1, S2)Merging Two Sorted Sequences
Merge-sort의 정복 단계는 두 개의 정렬된 시퀀스 A와 B를 병합하여 A와 B의 요소들을 포함하는 정렬된 시퀀스 S를 만드는 것임
- 두 개의 정렬된 시퀀스 A와 B를 병합하여 S를 생성함
- 각각 n/2 요소를 가진 두 정렬된 시퀀스를 병합하는 작업은 이중 연결 리스트(doubly linked list)를 사용하여 구현되며, O(n) 시간이 걸림
Algorithm merge(A, B)
Input sequences A and B with
n/2 elements each
Output sorted sequence of A ∪ B
S <- empty sequence
while A.isEmpty() ^ B.isEmpty()
if A.first().element() < B.first().element()
S.addLast(A.remove(A.first()))
else
S.addLast(B.remove(B.first()))
while A.isEmpty()
S.addLast(A.remove(A.first()))
while B.isEmpty()
S.addLast(B.remove(B.first()))
return SMerge-Sort Tree
Merge-sort의 실행은 이진 트리로 묘사됨
- 각 노드는 merge-sort의 재귀 호출을 나타내며 다음을 저장함:
- 실행 전의 정렬되지 않은 시퀀스와 그 분할
- 실행 후의 정렬된 시퀀스
- 루트는 초기 호출을 나타냄
- 리프 노드는 크기가 0 또는 1인 부분 시퀀스에 대한 호출을 나타냄
이진 트리 구조는 merge-sort의 단계별 과정을 시각적으로 나타내며, 각 단계에서 시퀀스가 어떻게 분할되고 병합되는지를 보여줌.
Analysis of Merge-Sort
Height of the Merge-Sort Tree: O(logn)O(\log n)O(logn)
- 각 재귀 호출에서 시퀀스를 반으로 나눔
Work Done at Nodes of Depth iii: O(n)O(n)O(n)
크기 2in인 2^i개의 시퀀스를 분할하고 병합함
n2i\frac{n}{2^i}
2^i+1개의 재귀 호출을 수행함
따라서, Merge-Sort의 총 실행 시간은 O(nlogn)O(n \log n)O(nlogn)임
정렬 알고리즘 요약
| 알고리즘 | 시간 복잡도 | 비고 |
|---|---|---|
| 선택 정렬 | O(n2)O(n^2)O(n2) | - 제자리 정렬 - 느림 (작은 입력에 적합 < 1K) |
| 삽입 정렬 | O(n2)O(n^2)O(n2) | - 제자리 정렬 - 느림 (작은 입력에 적합 < 1K) |
| 퀵 정렬 | O(nlogn)O(n \log n)O(nlogn) 예상 | - 제자리 정렬, 랜덤화 - 가장 빠름 (큰 입력에 적합 1K–1M) |
| 힙 정렬 | O(nlogn)O(n \log n)O(nlogn) | - 제자리 정렬 - 빠름 (큰 입력에 적합 1K–1M) |
| 병합 정렬 | O(nlogn)O(n \log n)O(nlogn) | - 온라인 정렬 (순차 데이터 접근) - 빠름 (매우 큰 입력에 적합 > 1M) |