알고리즘 [선택정렬 && 삽입정렬]
🔎 제자리(in-place)
어떠한 알고리즘을 수행할 때 제 2의 공간 즉, 현재의 공간을 제외한 다른 메모리를 추가적으로 사용하지 않고 현재의 공간만을 사용하여 알고리즘을 수행하는 것을 제자리(in-place)라고 한다.
익히 알고 있는 삽입정렬, 선택정렬 모두 제자리가 가능하고 1주차에서 설명한 정렬 제2의 공간을 활용한 정렬은 거의 사용하지 않는다. (이해를 돕기 위한 예시)
제 2의 공간의 기준은 n개의 메모리를 사용할 때 그 n개의 공간을 넘어서는 또다른 공간이 생긴 경우 제자리에서 수행한다고 볼 수 없다.
제자리 선택 정렬
리스트의 앞부분은 정렬 상태로 유지하며 리스트를 변경하는 대신 swap을 사용한다.
중요!
선택정렬은 마지막 전까지 비교하기 때문에 마지막 공간 즉, n-1을 반복한다.
실습
#include <stdio.h>
#define SIZE 10
int main()
{
int data[10] = {10,2,8,6,5,4,1,9,3,7};
int temp;
for (int i = 0; i < SIZE; i++) //정렬 전 출력
{
printf("%d ",data[i]);
}
printf("\n");
for (int i = 0; i < SIZE - 1; i++) //마지막까지 갈 필요 없음 선형반복
{
for (int j = i+1; j < SIZE; j++)
{
if(data[i]>data[j]) //오름차순 정렬
{
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
for (int i = 0; i < SIZE; i++) //정렬 후 출력
{
printf("%d ",data[i]);
}
printf("\n");
return 0;
}
결과: O(n²)
제자리 삽입 정렬
실습
#include <stdio.h>
#define SIZE 10
int main()
{
int data[10] = {10,2,8,6,5,4,1,9,3,7};
int temp,key,j;
for (int i = 0; i < SIZE; i++) //정렬 전 출력
{
printf("%d ",data[i]);
}
printf("\n");
for (int i = 1; i < SIZE; i++)
{
key = data[i]; //키값을 저장
for (j = i-1; j >= 0 && data[j] > key; j--)
{
data[j+1] = data[j]; //한칸씩 비교해서 큰수는 앞으로 민다.
}
data[j+1] = key; //스왑
}
for (int i = 0; i < SIZE; i++) //정렬 전 출력
{
printf("%d ",data[i]);
}
printf("\n");
return 0;
}
결과: O(n²)
내부 반복문은 선형탐색을 위주로 진행한다.
공통점
구현이 단순하고 작은 n에 대해 유용
++ 버블정렬은 많은 메모리를 잡아먹기 때문에 사용을 안하는 추세이다.
🔎 heap
힙이란, 내부노드에 키를 저장하며 힙순서와 완전이진트리의 속성을 만족하는 이진트리이다.(적정이진트리)
- 힙순서(heap-order): 루트를 제외한 모든 내부노드 v에 대해, key(v)≥key(parent(v))즉, 부모노드보다 큰값을 가진다.
- 완전이진트리(complete binary tree): 힙의 높이를 h라 하면 i = 0,…,h-1에 대해 깊이 n인 노드가 2ⁿ개 존재, 깊이 h-1에서 내부노드들은 외부노드들의 왼쪽에 존재
힙의 마지막 노드는 깊이 h-1의 가장 오른쪽 내부노드
힙을 사용하여 우선순위 큐 구현가능!
힙에 삽입
우선순위 큐 ADT의 메서드 insertitem은 힙에 키 k를 삽입하는 것에 해당한다.
총 3단계로 이루어 진다.
- 삽입노드 즉, 마지막 노드를 찾는다.
- k를 z에 저장한 후 expandExternal()작업을 사용하여 z를 내부노드로 확장(외부노드를 추가하여 내부노드로 확장)
- 힙순서 속성을 복구한다.
upheap upheap이라고 부르며 새로운 키값이 삽입되면 힙순서 숙성에 위배될 수 있다.(여기서는 부모보다 작은 값을 가짐)
upheap은 상향경로를 따라가며 교환함으로써 힙순서의 속성을 복구한다.
이때 부모의 키보다 작거나 같은 노드에 도달하면 종료하게 된다.
- 힙의 높이는 O(log n)이므로 upheap의 수행시간 또한 O(log n)수행
힙 삽입 및 upheap 알고리즘
Alg insertItem(k)
input key k, node last
output none
1. advanceLast()
2. z <- last
3. Set node z to k
4. expandExternal(z)
5. upHeap(z)
6. return
Alg upHeap(v)
input node v
output none
1. if (isRoot(v))
return
2. if (key(v) key(parent(v)))
return
3. swapElements(v, parent(v))
4. upHeap(parent(v))
외부노드를 추가하여 내부노드로 만드는 알고리즘
Alg expandExternal(z) {linked}
input external node z
output none
1. l <- getnode()
2. r <- getnode()
3. l.left <- null
4. l.right <- null
5. l.parent <- z
6. r.left <- null
7. r.right <- null
8. r.parent <- z
9. z.left <- l
10. z.right <- r
11. return
힙으로부터 삭제
우선순위 큐 ADT의 메서드 removeMin은 힙으로부터 루트 키를 삭제하는 것에 해당한다.
루트를 삭제하는 이유는 가장 작은 값을 삭제해야 하는데 루트의 키값이 가장 작은 값으로 정렬되어 있기 때문.
마찬가지로 3단계로 이루어진다.
- 루트 키를 마지막 노드 w의 키로 대체
- reduceExternl()작업을 사용해 그의 자식들을 외부노드로 축소한다.
- 힙 순서 속성을 복구
Downheap
루트 키를 마지막 노드의 키로 대체되면 힙순서 속성이 위배될 수 있다.
알고리즘 downheap은 루트로부터 하향경로를 따라가며 키를 교환함으로 힙순서 속성을 복구한다.
이때, 키가 잎에 또는 자식의 키가 k보다 크거나 같은 노드에 도달하면 정지한다.
마찬가지로 힙의 높이O(log n)이므로 downheap 수행시간 또한 O(log n)수행
Alg removeMin()
input node last
output key
1. k <- key(root())
2. w <- last
3. Set root to key(w)
4. retreatLast()
5. z <- rightChild(w)
6. reduceExternal(z)
7. downHeap(root())
8. return k
Alg downHeap(v)
input node v whose left and right subtrees are heaps
output a heap with root v
1. if (isExternal(leftChild(v)) & isExternal(rightChild(v)))
return
2. smaller <- leftChild(v) {internal node}
3. if (isInternal(rightChild(v)))
if (key(rightChild(v)) < key(smaller))
smaller <- rightChild(v)
4. if (key(v) ≤ key(smaller))
return
5. swapElements(v, smaller)
6. downHeap(smaller)
reduceExternal()작업 알고리즘
Alg reduceExternal(z) {linked}
input external node z
output the node replacing the parent node of the removed node z
1. w <- z.parent
2. zs <- sibling(z)
3. if (isRoot(w))
root <- zs {renew root}
zs.parent <- null
else
g <- w.parent
zs.parent <- g
if (w = g.left)
g.left <- zs
else {w = g.right}
g.right <- zs
4. putnode(z) {deallocate node z}
5. putnode(w) {deallocate node w}
6. return zs
구현
++ 추가 작성 필요
댓글남기기