섹션 1. 정렬
3. 기본적인 정렬 알고리즘
| 정렬 알고리즘 | |
| - Bubble sort - Insertion sort - Selection sort |
simple, slow |
| - Quicksort - Merge sort - Heap sort |
fast |
| - Radix sort | O(N) |
– Selection Sort
각 루프마다
- 최대 원소를 찾는다
- 최대 원소와 맨 오른쪽 원소를 교환한다
- 맨 오른쪽 원소를 제외한다
하나의 원소만 남을 때까지 위 루프를 반복
selectionSort(A[], n) // 배열 A[1...n]을 정렬한다.
{
for last <- n downto 2 { ---1
A[1...last] 중 가장 큰 수 A[k]를 찾는다; ---2
A[k] <-> A[last]; -> A[k] 와 A[last]의 값을 교환 ---3
}
}실행시간 :
①의 for 루프는 n-1번 반복
②에서 가장 큰 수를 찾기 위한 비교 횟수 : n-1, n-2, ..., 2.1
③의 교환은 상수시간 작업
시간복잡도 T(n) = (n-1) + (n-2) + ... + 2+1 = O(n^2)
– Bubble Sort
bubbleSort(A[], n) // 배열 A[1...n]을 정렬한다.
{
for last <- n downto 2 { ---1
for i <- 1 to last -1 ---2
if (A[i] > A[i+1]) then A[i] <-> A[i+1]; -> 교환 ---3
}
}수행시간:
①의 for 루프는 n-1번 반복
②의 for 루프는 각각 n-1, n-2,...,2,1번 반복
③의 교환은 상수시간 작업
시간복잡도 T(n) = (n-1) + (n-2) + ... + 2+1 = O(n^2)
– Insertion Sort
insertionSort(A[], n) // 배열 A[1...n]을 정렬한다.
{
for i <- 2 to n{ --- 1
A[1...n]의 적당한 자리에 A[i]를 삽입한다 --- 2
}
}수행시간:
①의 for 루프는 n-1번 반복
②의 삽입은 최악의 경우 i-1번 비교
최악의 경우 : T(n) = (n-1) + (n-2) + ... + 2+1 = O(n^2)
- 이건 최악의 경우를 계산한 것이기 때문에 평균적으로는 bubble sort와 selection sort의 절반정도 된다.
4. 합병정렬(merge sort)
merge sort 와 quick sort 는 분할정복법을 사용한다 (Divide and Conquer)
분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
정복 : 각각의 작은 문제를 순환적으로 해결
합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함
– merge sort
데이터가 저장된 배열을 절반으로 나눔
각각을 순환적으로 정렬
정렬된 두 개의 배열을 합쳐 전체를 정렬
mergeSort(A[], p, r) // A[p ... r]을 정렬한다.
{
if (p < r) then {
q <- (p+r) / 2; --- 1. p, r의 중간 지점 계산
mergeSort(A, p, q); --- 2. 전반부 정렬
mergeSort(A, q+1, r); --- 3. 후반부 정렬
merge(A, p, q, r); --- 4. 합병
}
}
merge(A[], p, q, r)
{
정렬되어 있는 두 배열 A[p...q]와 A[q+1...r]을 합하여
정렬된 하나의 배열 A[p....r]을 만든다.
}
최종 코드 :
void merge( int datap[], int p, int q, int r) {
int i = p; j = q+1; k = p;
int tmp[data.length()];
while (i <= q && j <= r) {
if (data[i] <= data[j])
tmp[k++] = data[i++];
else
tmp[k++] = data[j++];
}
while (i <= q)
tmp[k++] = data[i++];
while (j <= r)
tmp[k++] = data[j++];
for (int i = p; i <= r; i++)
data[i] = tmp[i];
}- 한쪽이 끝날 때까지 반복한다.
mergesort의 시간복잡도 : O(nlogn)
5. 빠른정렬(quick sort)
분할 : 배열을 다음과 같은 조건이 만족되도록 두 부분으로 나눈다.
elements in lower parts <= elements in upper parts
정복 : 각 부분을 순환적으로 정렬한다.
합병 : nothing to do
– Quicksort
정렬할 배열이 주어짐. 마지막 수를 기준(pivot)으로 삼는다
기준보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치(분할)한다 (partition)
기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다(정렬 완료)
quickSort(A[], p, r) // A[p...r]을 정렬한다
{
if (p<r) then {
// q : pivot의 위치
q = partition(A, p, r); // 분할
quickSort(A, p, q-1); // 왼쪽 부분배열 정렬
quickSort(A, q+1, r); // 오른쪽 부분배열 정렬
}
}
partition(A[], p, r)
{
// 배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치를 return 한다;
x <- A[r];
i <- p-1;
for j <- p to r-1 {
if A[j] <= x then
i <- i + 1;
exchange A[i] and A[j];
}
exchange A[i+1] and A[r];
return i+1;
}
어떻게 partition 할거냐?
if A[j] >= x
j <- j+1;
else
i <- i+1;
exchange A[i] and A[j];
j <- j+1;
quick sort 의 시간 복잡도
- 최악의 경우
항상 한 쪽은 0개, 다른 쪽은 n-1개로 분할되는 경우 O(n^2)
이미 정렬된 입력 데이터(마지막 원소를 피봇으로 선택하는 경우)
- 최선의 경우
항상 절반으로 분할되는 경우 O(nlogn)
확률의 기댓값을 이용하여 평균시간복잡도를 구해보면 O(nlogn) 이 된다.
pivot의 선택
- 첫번째 값이나 마지막 값을 피봇으로 선택
이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우
현실의 데이터는 랜덤하지 않으므로 (거꾸로) 정렬된 데이터가 입력으로 들어올 가능성은 매우 높음
따라서 좋은 방법이라고 할 수 없음
- median of three
첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 피봇으로 선택
최악의 경우 시간복잡도가 달라지지는 않음
- Randomized Quicksort
피봇을 랜덤하게 선택
no worst case instance, but worst case execution
평균 시간복잡도 O(NlogN)
6. 힙 정렬(heap sort)
최악의 경우 시간 복잡도 O(nlogn)
sorts in place - 추가 배열 불필요
이진 힙(binary heap) 자료구조를 사용
– Full vs Complete Binary Trees
full binary tree : 모든 레벨에 노드들이 꽉 차있는 형태
complete binary tree : 마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 가장 오른쪽부터 연속된 몇 개의 노드가 비어있을 수 있음
Heap은
1. complete binary tree이면서
2. heap property를 만족해야함
(max heap property : 부모는 자식보다 크거나 같다 / min heap property : 부모는 자식보다 작거나 같다)
힙은 유일하지 않다.
힙은 일차원 배열로 표현 가능 : A[1..n]
루트 노드 A[1]
A[i]의 부모 = A[i / 2]
A[i]의 왼쪽 자식 = A[2i]
A[i]의 오른쪽 자식 = A[2i+1]
- Max Heapify : recursive version
// 노드 i를 루트로하는 서브트리를 heapify 한다.
Max-Heapify(A, i)
{
if there is no child of A[i]
return;
k <- index of the diggest child of i;
if A[i] >= A[k]
return;
exchange A[i] and A[k];
Max-Heapify(A, k);
}
- Max Heapify : iterative version
Max-Heapify(A, i)
{
while A[i] has a child do
k <- index of the biggest child of i;
if A[i] >= A[k]
return;
exchange A[i] and A[k];
i = k;
end.
}
BUILD-MAX-HEAP(A)
heap-size[A] <- length[A]
for i <- length[A] / 2 down to 1
do Max-Heapify(A,i)
시간복잡도 : O(n)
– Heapsort
1. 주어진 데이터로 힙을 만든다.
2. 힙에서 최댓값(루트)을 가장 마지막 값과 바꾼다.
3. 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다.
4. 루트노드에 대해서 HEAPIFY(1)한다
5. 2~4번을 반복한다
HEAPSORT(A)
BUILD-Max-Heap(A) // O(n)
for i <- heap_size down to 2 do // n-1 times
exchange A[1] <-> A[i] // O(1)
heap_size <- heap_size - 1 // O(1)
Max-Heapify(A, 1) // O(logn)
// Total time = O(nlogn)
6-4. 힙의 다른 응용 : 우선순위 큐(priority queue)
- 최대 우선순위 큐 (maximum priority queue)는 다음의 두 가지 연산을 지원하는 자료구조
INSERT(x) : 새로운 원소 x를 삽입
EXTRACT_MAX() : 최댓값을 삭제하고 반환
- 최소 우선순위 큐 (minimum priority queue)는 EXTRACT-MAX 대신 EXTRACT-MIN을 지원하는 자료구조
- MAX HEAP을 이용하여 최대 우선순위 큐를 구현
- INSERT
MAX-HEAP-INSERT(A, key){
heap_size = heap_size + 1;
A[heap_size] = key;
i = heap_size;
while (i>1 and A[PARENT(i) < A[i]){
exchange A[i] and A[PARENT(i)];
i = PARENT(i);
}
}시간복잡도 O(logn)
- EXTRACT_MAX()
HEAP-EXTRACT-MAX(A)
if heap-size[A] < 1
then error "heap underflow"
max <-A[1]
A[1] <- A[heap-size[A]]
heap-size[A] <- heap-size[A] - 1
MAX-HEAPIFY(A,1)
return max시간복잡도 O(logn)
그래도 1학기 때 자료구조 때 배웠던 내용이라 익숙했고, 다시 한 번 들으니까 옛날에 들었을 때보다 이해가 더 빠릿빠릿 되었던 것 같다. 나중에 또 복습하고, 아이패드로 그려서 복습하자. 코드를 보고 이해하는 것에 더 나아가 내가 직접 코드를 구현할 수 있을 때까지 발전하고 싶다.
'공부기록 > 알고리즘' 카테고리의 다른 글
| 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch3.레드블랙트리 (0) | 2023.08.12 |
|---|---|
| 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch2.이진검색트리 (0) | 2023.08.05 |
| 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch1.정렬 #8~11 (0) | 2023.08.05 |
| 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch0.순환 #4~7 (0) | 2023.07.22 |
| 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch0.순환 #1~3 (0) | 2023.07.22 |
