C언어 정렬 shell, quick, heap sort 코드 구현, 정리
정렬 알고리즘에는 다양한 방법들이 있는데 이에 대해 알아보려고 한다.
기초적인 알고리즘으로 삽입정렬, 선택정렬, 버블정렬, 퀵정렬, 힙정렬, 합병정렬 등이 있으며
단순한 방법부터 알아보겠다.
단순한 방법
선택정렬 selection sort
구현방법
concept: n개의 원소를 가진 배열 list[]가 있다고 가정하자. 가장 작은 값부터 순차적으로 앞쪽으로 보낼 것이다.
반복문으로 배열을 순환하며 가장 작은 값을 꺼내 list[0] 값과 교환한다.
다시 정렬되지 않은 나머지 배열을 순환하며 그 중 최소값을 꺼내 list[1] 과 교환한다.
이를 반복하며 n-1번 반복하면 정렬이 완료된다.
#define SWAP(a, b, t) ((t)=(a), (a)=(b), (b)=(t))
void selection_sort(int list[],int n){
int i, j, least, temp;
for(int i=0;i<n;i++){
least = i;
for(int j=i+1;j<n;j++)
if(list[j]<list[least])
least = j;
SWAP(list[i],list[least],temp);
}
}복잡도
n개의 요소가 있을 때
비교횟수는 최소값을 찾는 과정에서 n-1번 비교, n-2번 비교, n-3번, ,,, ,1번 비교가 일어나기에 $\frac{n(n-1)}{2}$ 번 일어난다.
이동[교환]은 최소값을 찾고 n-1 번 두 값을 바꿔야 하는데 SWAP에서 3번의 교환이 일어나기에 $3(n-1)$ 번 발생한다.
때문에 전체 시간 복잡도는 $O(n^{2})$ 이다.
안정성
안정성을 만족하지 않는다.
삽입정렬 insertion sort
구현 방법
concept: 원소 하나씩 순회하며 값을 비교하며 앞쪽으로 보내는 방식이다.
마찬가지로 n개의 원소를 가진 배열을 가정한다. 비교할 원소를 key라 한다면 key 값을 배열의 인덱스를 1씩 증가시키며 바꿀 것이다. 우선 list[k] 값이 key 값이라면 이를 list[k-1]과 비교한다. key 값이 더 작다면 list[k-1] 값을 list[k]에 넣고 key 값을 list[k-2]와 비교할 것이다. 앞으로 나아가며 비교하다가 key값이 더 작지 않은 상황이 올 것이다. 이때 key 값을 빈 자리에 넣는 것이다.
void insertion_sort(int list[], int n){
int i, key;
for (i = 1; i<n; i++) {
int j = i-1;
key = list[i];
while(key<list[j] && j>=0){
list[j+1] = list[j];
j--;
}
list[j+1] = key;
}
}복잡도
비교횟수는 두 번째 값부터 비교하면서 앞쪽으로 보내기 때문에 1번, 2번, ,,, ,n-1번 비교한다.
[2번째 값을 앞으로 보낼때는 1번 비교, 3번째 값의 경우에는 최대 2번비교, 마지막 값의 경우에는 최대 n-1번 비교 가능]
때문에 최대 $\frac{n(n-1)}{2}$ 번 발생한다.
교환횟수는 앞으로 보낼 값을 key 변수에 n-1번 넣고[이동하고], 조건을 만족시키는 위치에 n-1번 배치[이동]하고
다른 앞에 있는 값들은 최대 $\frac{n(n-1)}{2}$ 번 이동한다. 때문에 $2(n-1)+\frac{n(n-1)}{2}$ 이므로 O(n^{2}) 이다.
안정성
안정성을 만족한다.
버블 정렬 bubble sort
구현방법
앞서 소개한 정렬이 가장 작은 값부터 차례대로 정렬했다면 이번에는 큰 값부터 정렬하는 방식이다.
concept: 처음 두 값을 비교하고 작은 값이 앞으로 오도록 교환한다.[뒤의 값이 더 크다면 유지] 그 다음 2, 3번 값을 비교하고 마찬가지로 작은 값이 앞으로 오도록 교환한다. n개의 원소에 대해 n-1 번 반복한다면 마지막 값에는 가장 큰 값이 들어갈 것이다. 정렬된 값을 제외하고 이를 반복한다.
처음에는 인덱스 0부터 n-1 까지 앞뒤 값을 비교하면서 교체한다.
다음 반복에서는 인덱스 0부터 n-2까지 비교하며 교체한다.
이를 반복하다 인덱스 0과 1의 값을 비교하고 교체한 후 정렬을 마친다.
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
void bubble_sort(int list[], int n)
{
int i, j, temp;
for (i = n - 1; i>0; i--) {
for (j = 0; j<i; j++)
if (list[j]>list[j + 1])
SWAP(list[j], list[j + 1], temp);
}
}복잡도
비교횟수는 n-1번 비교하면 마지막값이 확정되고, n-2번 비교하면 끝에서 두번째 값이 확정, ,,, ,2번, 1번 비교하면 끝나기에 $\frac{n(n-1)}{2}$ 번 비교한다.
이동[교환]횟수는 최악의 경우 비교할때마다 SWAP으로 교환하기에 3*비교횟수 이므로 $\frac{3n(n-1)}{2}$ 번이다.
때문에 $O(n^{2})$ 의 시간복잡도를 가진다.
안정성
안정성을 만족한다.
다음으로는 조금 더 복잡하지만 효율적인 방법을 알아볼 것이다.
효율적인 방법
shell sort
삽입 연산의 개선 버전이라 생각할 수 있다.
구현방법
concept: 배열을 일정 간격으로 나누고 각 부분[segment]들에 대해 삽입 정렬을 실시한다. 실시한 후 간격을 반으로 줄여나가며 실시한다. 간격이 1이 되었을 때 정렬을 종료한다.
우선 세그먼트 하나에 대한 정렬을 하는 함수를 정의한다.
일정한 간격인 gap이 선언되어 있다. gap이 5라면 key를 list[5]라고 하고
key가 list[0]보다 작으면 list[5]에 list[0]을 넣는다.
- 반복문 (첫 번째 for loop):
- i는 first + gap부터 시작하여 last까지 gap씩 증가합니다. 즉, 간격만큼 건너뛰면서 배열을 순차적으로 확인합니다.
- 이 반복문은 gap 간격으로 요소들을 탐색하고, 해당 요소를 삽입할 위치를 찾습니다.
-
for (i = first + gap; i <= last; i = i + gap)
- key 선택:
- i번째 요소를 key에 저장합니다. 이 값은 현재 삽입할 값이 됩니다.
-
key = list[i];
- 두 번째 반복문 (삽입 위치 찾기):
- key보다 큰 값을 왼쪽에서 찾아서 한 칸씩 오른쪽으로 밀어냅니다.
- j는 i - gap부터 시작하여, key보다 큰 값을 찾아 j = j - gap을 이용해 gap만큼 건너뛰면서 진행됩니다.
- 만약 key보다 큰 값이 있으면 그 값을 오른쪽으로 밀어냅니다. 이 과정은 삽입 정렬에서 key의 위치를 찾아가는 과정과 유사합니다.
-
for (j = i - gap; j >= first && key < list[j]; j = j - gap) list[j + gap] = list[j];
- key 삽입:
- key를 j + gap 위치에 삽입합니다. 즉, key보다 큰 모든 값들은 오른쪽으로 밀리고, key는 빈 공간에 적절히 삽입됩니다.
-
list[j + gap] = key;
void shell_sort(int list[], int n) // n = size
{
int i, gap;
for (gap = n / 2; gap>0; gap = gap / 2) {
printf("gap:%d\n", gap);
if ((gap % 2) == 0) gap++;
for (i = 0; i<gap; i++) // 부분 리스트의 개수는 gap
inc_insertion_sort(list, i, n - 1, gap);
print_list(list);
}
}복잡도
첫 번째 정렬 시
최악의 경우 $O(n^{1.5})$
퀵정렬 quick sort
구현방법
concept: 퀵정렬은 교환 정렬의 개선 버전이라 생각할 수 있다. 배열에서 기준 값(pivot)을 잡고 피봇보다 작은 값은 왼쪽, 큰 값은 오른쪽에 넣는다. 그리고 왼쪽, 오른쪽의 나머지 값에서도 각각 똑같이 진행하면 정렬할 수 있다.
우선 배열에서 가장 왼쪽 값을 피봇 값으로 잡는다. 중앙값을 피봇으로 잡으면 좋지만 편의상 왼쪽 값을 잡은 것일뿐 어떤 값도 상관은 없다. 그리고 피봇을 제외한 첫 번째 값을 low, 마지막 값을 high 로 칭한다.
low에서 인덱스를 증가시키며 피봇값보다 작은지 확인한다. 만약 큰 값이라면 멈추고 high 인덱스 값을 감소시키며 피봇과 비교한다. high 값이 피봇보다 작다면 low 값과 high 값을 서로 교환해준다.
차차 진행하다가 마지막엔 low 인덱스가 high 인덱스보다 커지는 순간이 생길 것이다. 이때 반복을 멈추고 high 인덱스에 있는 값과 피봇이 위치한 list[0]을 바꿔 피봇이 중앙에 위치하도록 한다.
#define SWAP(a, b, t) ((t)=(a), (a)=(b), (b)=(t))
void quick(int list[], int start, int end){
int low=start+1;
int high=end;
int temp;
while(low<high){
while(list[low]<list[start]){
low++;
}
while(list[high]>list[start]){
high--;
}
SWAP(list[low],list[high],temp)
}
quick(list, start, high-1);
quick(list, high+1, end);
}복잡도
최선의 경우 O(nlogn)
최악의 경우(피봇이 끝에 있는 경우) pivot을 선택하는 경우가 n-1번, 한 번에 n-1 ~ 1번 비교하기에 시간복잡도는 O(n^{2}) 이다.
힙정렬 heap sort
구현방법
Max heap에 대해 설명할텐데 max heap은 부모 노드의 값이 자식 노드의 값 이상인 완전 이진 트리이다.
이때 완전 이진 트리는 왼쪽부터 값이 완벽하게 채워진 이진트리이다.
힙정렬은 트리를 만드는 삽입과 트리에서 값을 제거하며 정렬된 배열을 만드는 삭제로 이루어져있다.
때문에 삽입, 삭제 함수를 만들고 두 함수를 이용해 정렬 함수를 만든다.
함수 C언어 구현
삽입의 컨셉은 우선 값을 트리의 말단에 넣고 부모와 비교하면서 값이 크다면 부모 노드와 교환하며 올라가는 방식이다.
void insert_max_heap(HeapType* h, element item)
{
int i;
i = ++(h->heap_size);
// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
while ((i != 1) && (item.key > h->heap[i / 2].key)) {
h->heap[i] = h->heap[i / 2];
i /= 2;
}
h->heap[i] = item; // 새로운 노드를 삽입
}삭제의 컨셉은 root 노드를 삭제하고 말단 노드를 root 노드에 올린다. 그리고 자식 노드를 root에 있는 값과 비교하면서 max heap을 성질을 만족할때까지 노드를 교체하며 내려간다. 내려갈 때는 자식 중 더 큰 값을 찾고 그 자식과 바꿔가며 내려간다.
완료가 되면 기존 삭제된 노드의 값을 반환할 것이다.
element delete_max_heap(HeapType* h)
{
int parent, child;
element item, temp;
item = h->heap[1];
temp = h->heap[(h->heap_size)--];
parent = 1;
child = 2;
while (child <= h->heap_size) {
if ((child < h->heap_size) &&
(h->heap[child].key) < h->heap[child + 1].key)
child++;
if (temp.key >= h->heap[child].key) break;
// 한 단계 아래로 이동
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
h->heap[parent] = temp;
return item;
}정렬 함수에서 우선 삽입함수를 n번 반복해 하나하나씩 트리를 만들어줄 것이다. 이후 삭제함수를 n번 반복해 반환된 값을 배열의 끝부터 넣어줄 것인데, 이렇게 한다면 오름차순 정렬된 배열이 만들어질 것이다.
void heap_sort(element a[], int n)
{
int i;
HeapType* h;
h = create();
init(h);
for (i = 0; i<n; i++) {
insert_max_heap(h, a[i]);
}
for (i = (n - 1); i >= 0; i--) {
a[i] = delete_max_heap(h);
}
free(h);
}복잡도
이진트리이기에 삽입에서는 logn, log(n-1) ... log(1)
최종 $O(nlogn)$$