[책 정리] Chapter 09. 정렬

9.1 정렬이란?

정렬(sorting): 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미
레코드(record): 정렬시켜야 될 대상
필드(field): 레코드가 더 작은 단위로 나눠짐
키(key): 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드

정렬 알고리즘
1. 단순하지만 비효율적인 방법 - 삽입 정렬, 선택 정렬, 버블 정렬 등
2. 복잡하지만 효율적인 방법 - 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬 등
3. 내부 정렬(internal sorting): 모든 데이터가 주기억장치에 저장된 상태에서 정렬하는 것
4. 외부 정렬(external sorting): 외부기억장치(하드디스크)에 대부분의 데이터가 있고 일부만 주기억장치에 저장된 상태에서 정렬하는 것
5. 안정성(stability): 입력 데이터에 동일한 키 값을 갖는 레코드가 여러 개 존재할 경우, 이들 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음을 뜻함 -> 삽입 정렬, 합병 정렬
6. 안정성X: 같은 키 값을 갖는 레코드들이 정렬 후에 위치가 바뀌게 되면 안정하지 않다고 함

9.2 선택 정렬

선택 정렬의 원리

선택 정렬(selection sort)
1. 왼쪽 리스트와 오른쪽 리스트의 두 개의 리스트가 있다고 가정
2. 왼쪽 리스트에는 정렬이 완료된 숫자들이 들어 있고 오른쪽에는 정렬되지 않은 숫자들이 들어 있음
3. 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 오른쪽 리스트가 공백 상태가 될 때까지 되풀이 함

왼쪽 리스트	오른쪽 리스트	설명
()	(5,3,8,1,2,7)	초기 상태
(1)	(5,3,8,2,7)	1 선택
(1,2)	(5,3,8,7)	2 선택
(1,2,3)	(5,8,7)	3 선택
(1,2,3,5)	(8,7)	5 선택
(1,2,3,5,7)	(8)	7 선택
(1,2,3,5,7,8)	()	8 선택

-> 이 방법을 구현하기 위해서는 입력 배열과는 별도로 똑같은 크기의 배열이 하나 더 필요함
-> 메모리 공간을 추가로 사용하는 것이므로 메모리 절약을 위한 새로운 정렬 방법이 필요

제자리 정렬(in-place sorting): 입력 배열 이외에는 다른 추가 메모리를 요구하지 않는 정렬 방법
1. 입력 배열에서 최솟값을 발견한 다음, 이 최솟값을 배열의 첫 번째 요소와 교환
2. 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두 번째 요소와 교환
3. 이 절차를 (숫자 개수-1)만큼 되풀이하면 추가적인 배열을 사용하지 않고서도 전체 숫자들이 정렬됨

선택 정렬 알고리즘

i값이 0에서 n-2까지만 변화 됨 -> A[0]부터 A[n-2]까지 정렬 되었으면 이미 A[n-1]이 가장 큰 값이기 때문

<알고리즘 9.2.1> 선택 정렬 알고리즘

selection_sort(A,n)

for i <- 0 to n-2 do
	least <- A[i], A[i+1],...,A[n-1] 중에서 가장 작은 값의 인덱스;
    A[i]와 A[least]의 교환;
    i++;

<프로그램 9.2.1> 선택 정렬 함수

#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))

void selection_sort(int list[], int n){
	int tmp;
    for(int i=0;i<n-1;i++){
    	least = i;
        for(int j= i+1;j<n-2;j++){ // 최솟값 탐색
        	if(list[j] < list[least]) least = j;
        }
        SWAP(list[i],list[j],tmp);
    }
}

전체 프로그램

<프로그램 9.2.2> 선택 정렬 프로그램

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10 // 기존 코드 10000
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

int list[MAX_SIZE];
int n;

void selection_sort(int list[], int n)
{
    int tmp;
    int least;
    for (int i = 0; i < n - 1; i++) {
        least = i;
        for (int j = i + 1; j < n; j++) {
            if (list[least] > list[j]) {
                least = j;
            }
        }
        SWAP(list[i], list[least], tmp);
    }
}

int main()
{
    n = MAX_SIZE;
    for (int i = 0; i < n; i++) { // 난수 생성
        list[i] = rand() % n; // 난수 발생 범위 0 ~ n-1
    }

    printf("Before: ");
    for (int i = 0; i < n; i++) { // 정렬 결과 출력
        printf("%d ", list[i]);
    }
    printf("\n");

    selection_sort(list, n); // 선택 정렬 호츌

    printf("After: ");
    for (int i = 0; i < n; i++) { // 정렬 결과 출력
        printf("%d ", list[i]);
    }
    printf("\n");
}

선택 정렬의 분석

1. 비교 횟수: 2개의 for 루vm의 실행 횟수를 계산
   외부 루프: n-1
   내부 루프: (n-1)-i
   전체 비교 횟수: n(n-1)/2
   시간복잡도: $O(n^2)$

2. 이동 횟수: 외부 루프의 실행 횟수와 같으며 한번 교환 시 3번의 이동이 필요하므로
   전체 이동 회수: 3(n-1)

선택 정렬의 장점: 자료 이동 횟수가 미리 결정됨

선택 정렬의 문제점
-안정성을 만족하지 않음(값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있음)
-자료가 정렬된 경우에는 자기 자신과의 교환을 하게 됨 -> 이를 해결하기 위해서 아래의 if문을 추가하면 됨

// 최소값이 자기 자신이면 이동하지 않음
if(i != least){ 
	SWAP(list[i],list[least],tmp);
}

9.3 삽입 정렬

삽입 정렬의 원리

삽입 정렬(insertion sort): 정렬되어 있는 리스트에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복

• 입력 배열을 정렬된 리스트(왼쪽 리스트)와 정렬되지 않은 리스트(오른쪽 리스트)로 나누어 사용
• 정렬되지 않은 리스트(오른쪽 리스트)의 첫번째 숫자가 정렬된 리스트(왼쪽 리스트)의 어느 위치에 삽입되어야 하는가를 판단한 후 해당 위치에 이 숫자를 삽입

삽입 정렬의 알고리즘

<알고리즘 9.3.1> 삽입 정렬 알고리즘

insertion_sort(A,n)

for i <- 1 to n-1 do // 인덱스 1부터 시작, 인덱스 0은 이미 정렬된 것으로 볼 수 있음
	key <- A[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
    j <- i-1; // 현재 정렬된 배열은 i-1까지이므로, i-1번째부터 역순으로 조사
    while j >=0 and A[j] > key do // j가 음수가 아니고, key값 보다 정렬된 배열에 있는 값이 크면 
    	A[j+1] = A[j]; // j번째를 j+1번째로 이동
        j <- j-1; // j는 하나 감소
    A[j+1] <- key // j번째 정수가 key보다 작으므로 j+1번째가 key 값이 들어갈 위치임

삽입 정렬의 C언어 구현

<프로그램 9.3.1> 삽입 정렬 프로그램

void insertion_sort(int list[], int n){
	int tmp;
    int j;
    for(int i=1;i<n;i++){
    	key = list[i];
    	for(j= i-1; j>=0 && list[j] > key;j--){
        	list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
        }
        //j = i-1;
        //while ((j>=0) && (list[j] > key)){
        //	list[j+1] = list[j];
        //    j -= 1;
        //}
        list[j+1] = key;
    }
}

삽입 정렬의 복잡도 분석

1. 입력 자료가 정렬된 경우 가장 빠름
   외부 루프 n-1
   총 비교 횟수 n-1 -> 이동 없이 비교만 1번 함
   시간복잡도 $O(n)$

2. 입력 자료가 역순일 경우 최악 -> 각 단계에서 앞에 놓인 자료들은 전부 한 칸씩 뒤로 이동해야 함
   총 비교 횟수 n(n-1)/2, 시간복잡도 $O(n^2)$
   총 이동 횟수 n(n-1)/2+2(n-1), 시간복잡도 $O(n^2)$

삽입 정렬 단점: 비교적 많은 레코드들의 이동이 포함됨 -> 레코드 크기가 클 경우 적합하지 않음
삽입 정렬 장점: 안전한 정렬 방법, 이미 정렬되어 있는 경우에 매우 효율적

9.4 버블 정렬

버블 정렬의 원칙

버블 정렬(bubble sort)
1. 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행
2. 이러한 비교-교환 과정(스캔)이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동됨

버블 정렬의 알고리즘

<알고리즘 9.4.1> 버블 정렬 알고리즘

BubbleSort(A,n)
for i <- n-1 to 1 do
	for J <- 0 to i-1 do
    	j와 j+1번째의 요소가 크키순이 아니면 교환
        j++;
    i--;

버블 정렬 C언어 구현

<프로그램 9.4.1> 버블 정렬 프로그램

#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))
void bubble_sort(int list[], int n){
	int tmp;
	for(int i=n-1;i>0;i--){
    	for(int j=0;j<i;j++){
        	if(list[j] > list[j+1]){ // 앞뒤의 레코드를 비교한 후 교체
            	SWAP(list[j],list[j+1],tmp);
            }
        }
    }
}

버블 정렬의 복잡도 분석

1. 비교 횟수 -> 버블 정렬은 최상, 평균, 최악 어떤 경우에도 항상 일정
   총 비교 횟수 n(n-1)/2
   시간복잡도 $O(n^2)$

2. 이동 횟수 -> 입력 자료가 역순으로 정렬되어 있을 경우 최악, 입력 자료가 이미 정렬되어 있는 경우 최상
   총 이동 횟수 3*총 비교 횟수
   시간복잡도 $O(n^2)$

버블 정렬 문제점: 순서에 맞지 않은 요소를 인접한 요소와 교환하는것 -> 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 함, 특히, 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어남
-> 자료의 교환(swap) 작업이 자료의 이동(move) 작업보다 더 복잡하기 때문에 버블 정렬은 그 단순성에도 불구하고 거의 사용하지 않음

9.5 셸 정렬

셸 정렬의 원리

셸 정렬(shell sort): 삽입 정렬의 문제(요소 삽입 시 이웃한 위치로만 이동한다는 문제: 삽입 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있음)를 보완한 정렬 방법 -> 셸 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있음

• 셸 정렬은 삽입 정렬과 달리 전체 리스트를 한 번에 정렬하지 않음

1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만듦
2. 각 부분 리스트를 삽입 정렬을 이용하여 정렬
3. 모든 부분 리스트가 정렬되면 셸 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만듦
4. 이는 부분 리스트의 개수가 1일 될 때까지 되풀이 함

부분 리스트 구성
-주어진 리스트의 각 k번째 요소(k = 간격(gap))를 추출하여 만듦

입력 배열	10	8	6	20	4	3	22	1	0	15	16
간격 5일 때의 부분 리스트	10					3					16
	8					22
		6					1
			20					0
				4					15
부분 리스트 정렬 후	3					10					16
	8					22
		1					6
			0					20
				4					15
간격 5 정렬 후의 전체 배열	3	8	1	0	4	10	22	6	20	15	16
간격 3일 때의 부분 리스트	3			0			22			15
	8			4			6			16
		1			10			20
부분 리스트 정렬 후	0			3			15			22
	4			6			8			16
		1			10			20
간격 3 정렬 후의 전체 배열	0	4	1	3	6	10	15	8	20	22	16
간격 1 정렬 후의 전체 배열	0	1	3	4	6	8	10	15	16	20	22

셸 정렬의 구현

<프로그램 9.5.1> 셸 정렬 구현

// gap 만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last
void inc_insertion_sort(int list[], int first, int last, int gap){
	for(int i = first+gap;i<=last; i = i+gap){
    	key = list[i];
        for(int j = i-gap; j >=first && key <list[j];j=j-gap){
        	list[j+gap] = list[j];
        }
        list[j+gap] = key;
    }
}

void shell_sort(int list[], int n){ // n = size
	for(int gap = n/2;gap >0;gap = gap/2){ // 간격은 처음에 n/2로 하고 각 패스마다 간격을 절반으로 줄이는 방식을 사용
    	if(gap%2 == 0) gap++; // 간격이 짝수이면 1을 더하는 것이 좋은 것으로 분석
        for(int i=0;i<gap;i++){ // 부분 리트의 개수는 gap
        	inc_insertion_sort(list,i,n-1,gap);
        }
    }
}

셸 정렬의 분석

셸 정렬의 장점
1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동함 <-> 삽입 정렬에서는 한 번에 한 번에 한 칸씩만 이동됨
-> 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아짐
2. 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되면 셸 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 더욱 빠르게 수행됨(삽입 정렬이 거의 정렬된 파일에 대해서는 빠르게 수행되기 때문)

시간복잡도 최악 $O(n^2)$, 평균 $O(n^1.5)$

9.6 합병 정렬

합병 정렬의 개념

합병 정렬(merge sort): 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합
하여 전체가 정렬된 리스트가 되게 하는 방법 -> 분할 정복 방법에 바탕을 두고 있음
분할 정복(divide and conquer): 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할
2. 정복(Conquer): 부분 배열을 정렬, 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병

합병 정렬 알고리즘

<알고리즘 9.6.1> 합병 정렬 알고리즘

merge_sort(list, left, right)

if left < right then // 만약 나누어진 구간의 크기가 1 이상이면
	mid = (left+right)/2; // 중간 위치를 계산 
    merge_sort(list, left, mid); // 앞쪽 부분 배열을 정렬하기 위해 merge_sort 함수를 순환 호출
    merge_sort(list, mid+1, right); // 뒤쪽 부분 배열을 정렬하기 위해 merge_sort 함수를 순환 호출
    merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 통합하여 하나의 정렬된 배열로 만듦

• 2개의 리스트를 합병(merge)하는 단계: 실제로 정렬이 이루어지는 시점

1. 2개의 요소들을 처음부터 하나씩 비교하여 두 개의 리스트의 요소 중 더 작은 요소를 새로운 리스트로 옮김
2. 둘 중 하나가 끝날 떄까지 이 과정을 되풀이 함
3. 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 요소들을 전부 새로운 리스트로 복사하면 됨

<알고리즘 9.6.2> 합병 알고리즘

merge(list, left, mid, right)
// 2개의 인접한 배열 list[left..mid]와 list[mid+1..right]를 합병

i <- left;
j <- mid + 1;
k <- left;
sorted 배열을 생성; // 합병된 리스트를 임시로 저장하기 위한 배열

while i <= mid and j<= right do
	if(list[i] < list[j])
    	then
        	sorted[k] <- list[i];
        	k++;
            i++;
       	else
        	sorted[k] <- list[j];
            k++;
            j++;
 요소가 남아있는 부분배열을 sorted로 복사함;
 sorted를 list로 다시 복사;

합병 정렬의 C언어 구현

<프로그램 9.6.1> merge 알고리즘 구현

#include <stdio.h>
#define MAX_SIZE 8
void merge(int list[], int left, int mid, int right)
{
    int i = left; // i는 정렬된 왼쪽 리스트에 대한 인덱스
    int j = mid + 1; // j는 정렬된 오른쪽 리스트에 대한 인덱스
    int k = left; // k는 정렬될 리스트에 대한 인덱스

    int sorted[MAX_SIZE];

    // 분할 정복된 list의 합병
    while (i <= mid && j <= right) {
        if (list[i] <= list[j]) {
            sorted[k++] = list[i++];
        } else {
            sorted[k++] = list[j++];
        }
    }

    // 남아 있는 레코드 일관 복사
    if (i <= mid) {
        for (int p = i; p <= mid; p++) {
            sorted[k++] = list[p];
        }
    } else {
        for (int p = j; p <= right; p++) {
            sorted[k++] = list[p];
        }
    }

    // 배열 sorted[]의 리스트를 배열 list[]로 재복사
    for (int p = left; p <= right; p++) {
        list[p] = sorted[p];
    }
}

void merge_sort(int list[], int left, int right)
{
    if (left < right) {
        int mid = (left + right) / 2; // 리스트의 균등 분할
        merge_sort(list, left, mid); // 부분 리스트 정렬
        merge_sort(list, mid + 1, right); // 부분 리스트 정렬
        merge(list, left, mid, right); // 합병
    }
}

int main(){
    int list[MAX_SIZE] = { 27, 10, 12, 20, 25, 13, 15, 22 };
    merge_sort(list, 0, MAX_SIZE-1);
    for (int i = 0; i < MAX_SIZE;i++){
        printf("%d ", list[i]);
    }
    printf("\n");

    return 0;
}

합병 정렬 복잡도 분석

1. 비교 횟수
   분할 단계: $n=2^k$ 인 레코드가 있으면, 순환 호출의 깊이가 k가 된다는 것을 알 수 있음.
   합병 단계: 최대 n번의 비교 연산이 필요함
   총 비교 횟수: 합병 단계가 k($k=logn$)번 만큼 있으므로 $nlogn$

2. 이동 횟수
   총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드 이동 2n번 발생
   총 이동 횟수: 합병 단계가 k번 만큼 있으므로 $2nlogn$

시간복잡도 $O(nlogn)$

합병 정렬의 장점: 안정적인 정렬 방법으로 데이터의 분포에 영향을 덜 받음. 즉, 입력 데이터가 무엇이든 간 정렬되는 시간은 동일
합병 정렬의 단점: 임시 배열이 필요함, 레코드의 크기가 큰 경우 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래함(-> 연결 리스트를 사용하면 링크 인덱스만 변경되므로 데이터 이동은 무시할 수 있을 정도로 작아짐)

9.7 퀵 정렬

퀵 정렬의 개념

퀵 정렬(quick sort): 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용
1. 리스트 내에 있는 한 요소를 피벗(pivot)으로 선택
2. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨짐
3. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성되고, 오른쪽은 피벗보다 큰 요소들로 구성됨
4. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬됨

퀵 정렬 알고리즘

<프로그램 9.7.1> 퀵 정렬

void quick_sort(int list[], int left, int right){
	if(left < right){ // 정렬할 범위가 2개 이상의 데이터라면
    	int q = partition(list, left, right); // partition 함수를 호출하여 피벗을 기준으로 2개의 리스트로 분할, partition 함수의 반환 값을 피벗의 위치가 됨
        quick_sort(list, left, q-1); // left에서 피벗 위치 바로 앞까지를 대상으로 순환 호출(피벗은 제외됨)
        quick_sort(list, q+1, right); // 피벗 위치 바로 다음부터 right까지를 대상으로 순환 호출(피벗은 제외됨)
    }
}

Partition 함수

• Partition 함수는 데이터가 들어 있는 배열 list의 left부터 right까지의 리스트를 피벗을 기준으로 2개의 부분 리스트로 나누게 됨
• 피벗보다 작은 데이터는 모두 왼쪽 부분 리스트로, 큰 데이터는 모두 오른쪽 부분 리스트로 옮겨짐

<프로그램 9.7.2> partition 함수

int partition(int list[], int left, int right){
	int pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택
    int low = left; // low는 left+1에서 출발, do-while 루프에서 먼저 증가시킴을 주의
    int high = right+1; // high는 right에서 출발, do-while 루프에서 먼저 감소시킴을 주의
    int tmp;
    
    do{ // low와 high가 교차할 때까지 방복
    	
        // list[low]가 pivot보다 작으면 계속 low를 증가시킴
        do{
        	low++;
        }while( low <= right && list[low] < pivot);
        
        // list[high]가 pivot보다 크면 계속 high를 감소시킴
        do{
        	high--;
        }while(high >=left && list[high] > pivot);
        
        // low와 high가 아직 교차하지 않았으면 list[low]와 list[high]를 교환
        if(low < high){
        	SWAP(list[low], list[high], tmp);
        }
    }while(low < high); // 만약 low와 high가 교차했으면 반복을 종료
    
    SWAP(list[left],list[high],tmp); // list[left]와 list[high]를 교환
    return high; // 피벗의 위치인 high를 반환
}

전체 프로그램

<프로그램 9.7.3> 퀵 정렬

#include <stdio.h>

#define MAX_SIZE 100
int n = 9;
int list[MAX_SIZE] = { 5, 3, 8, 4, 9, 1, 6, 2, 7 };
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

int partition(int list[], int left, int right)
{
    int pivot = list[left];
    int low = left;
    int high = right + 1;
    int tmp;

    do{
        do{
            low++;
        } while (low <= right && list[low] < pivot);
        do{
            high--;
        } while (high >= left && list[high] > pivot);
        if(low < high){
            SWAP(list[low], list[high], tmp);
        }
    } while (low < high);
    SWAP(list[left], list[high], tmp);
    return high;
}

void quick_sort(int list[], int left, int right){
    if(left < right){
        int q = partition(list, left, right);
        quick_sort(list, left, q - 1);
        quick_sort(list, q + 1, right);
    }
}

int main(){
    quick_sort(list, 0, n - 1);
    for (int i = 0; i < n;i++){
        printf("%d ", list[i]);
    }
    printf("\n");
    return 0;
}

퀵 정렬의 복잡도 분석

시간복잡도 평균의 경우 $O(nlogn)$, 최악의 경우 $O(n^2)$

퀵 정렬의 장점: 속도가 빠르고, 추가 메모리 공간을 필요로 하지 않음
퀵 정렬의 단점: 정렬된 리스트에 대해서는 오히려 수행시간이 더 많이 걸림(-> 피벗 선택 방법(ex) 중간 값(median) 선택)을 바꿈)

퀵 정렬 라이브러리 함수의 사용

C언어 실행 시간 라이브러리에 큌 정렬 함수가 제공됨 -> qsort 함수

• 함수의 원형

void qsort(void *base, size_t num, size_t width, int(*compare)(const void*, const void*));

• 함수의 파라미터 설명
  • base: 배열의 시작 주소
  • num: 배열 요소의 개수
  • width: 배열 요소 하나의 크기(바이트 단위)
  • compare: 비교 함수. 포인터를 통하여 두 개의 요소를 비교하여 비교 결과를 정수로 반환, 사용자가 제공해야 함
• 함수의 설명
  각 요소는 width 바이트인 num개의 요소를 가지는 배열에 대해 퀵 정렬을 수행

// compare 함수 호출 방법
compare((void *)elem1, (void*)elem2);

반환 값	설명
< 0	elem1이 elem2보다 작으면
0	elem1이 elem2와 같으면
> 0	elem1이 elem2보다 크면

• 함수의 사용 예

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* arg1, const void* arg2)
{
    if (*(double*)arg1 > *(double*)arg2)
        return 1;
    else if (*(double*)arg1 == *(double*)arg2)
        return 0;
    else
        return -1;
}

int main()
{
    double list[5] = { 2.1, 0.9, 1.6, 3.8, 1.2 };
    qsort((void*)list, (size_t)5, sizeof(double), compare);
    for (int i = 0; i < 5; i++) {
        printf("%.1f ", list[i]);
    }
    printf("\n");
    return 0;
}

9.8 힙 정렬

힙 정렬 개념

힙: 우선순위 큐를 완전 이진 트리로 구현하는 방법으로 힙은 최댓값이나 최솟값을 쉽게 추출할 수 있는 자료구조
힙 정렬: 최소 힙의 특성(부모 노드의 값 < 자식 노드의 값)을 이용하여 정렬한 배열을 먼저 회소 힙으로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법
=> 최소 힙을 만들고 숫자들을 차례대로 삽입한 당, 최솟값부터 삭제하면 됨

9.9 기수 정렬

기수 정렬의 원리

기수 정렬(radix sort)은 입력 데이터에 대해 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 정렬 기법이고, 시간복잡도 $O(dn), d < 10$임

기수 정렬의 장점: 다른 정렬 기법 보다 빠름
기수 정렬의 단점: 추가 메모리가 필요, 정렬할 수 있는 레코드의 타입이 한정됨 -> 레코드의 키들이 동일한 길이를 가지는 숫자 문자열로 구성되어 있엉 함

기수(radix): 숫자의 자릿수
기수 정렬: 자릿수의 값에 따라 정렬함, 다단계 정렬, 단계의 수는 데이터의 자릿수 개수와 일치
ex) 한 자릿수의 숫자 정렬
1. 십진수에서는 각 자릿수가 0에서 9까지의 값만 있으므로, 10개의 버켓(bucket)을 만들어서 입력 데이터를 각 자릿수의 값에 따라 베켓에 넣음
2. 위에서부터 아래로 순차적으로 버켓 안에 들어 있는 숫자들을 읽음으로써 정렬된 숫자 리스트를 얻을 수 있음

ex) 두 자릿수의 숫자 정렬

• 0 ~ 99번까지의 100개 버켓을 사용하여 앞의 방법과 마찬가지로 정렬할 수 있음
• 0 ~ 9까지의 10개 버켓을 사용하여 정렬할 수 있음
  -> 1의 자릿수를 먼저 사용하고, 10의 자릿수를 사용하면 됨
  

기수 정렬 알고리즘

LSD(least significant digit): 가장 낮은 자릿수
MSD(most significant digit): 가장 높은 자릿수

<알고리즘 9.9.1> 기수 정렬 알고리즘

RadixSort(list,n):

for d <- LSD의 위치 to MSD의 위치 do
{
	d번째 자리수에 따라 0번부터 9번 버켓에 넣음
    버켓에서 숫자들을 순차적으로 읽어서 하나의 리스토로 합침
    d++;
}

• 각각의 버켓에서 먼저 들어간 숫자들은 먼저 나와야 함 -> 각각의 버켓은 큐로 구현되어야 함
• 버켓에 숫자를 넣는 연산은 큐의 삽입 연산이 되고 버켓에서 숫자를 읽는 연산은 삭제 연산으로 대치됨
• 버켓의 개수: 키의 표현 방법과 밀접한 관계 있음
  키가 2진법: 버켓 2개
  키가 알파벳: 버켓 26개
  키가 숫자: 버켓 10개
  

기수 정렬 구현

<프로그램 9.9.1> 기수 정렬 프로그램

// 6장 queue source
#include <stdio.h>
#define BUCKETS 10 // 10개의 버켓이 필요
#define DIGITS 4 // 4자리로 된 정수만 취급
#define MAX_QUEUE_SIZE 100

// 원형 큐
typedef int element;
typedef struct{
    element queue[MAX_QUEUE_SIZE];
    int front, rear;
} QueueType;

void init(QueueType *q){
    q->front = 0;
    q->rear = 0;
}

int is_empty(QueueType *q){
    return (q->front == q->rear);
}

int is_full(QueueType *q){
    return ((q->rear + 1 % MAX_QUEUE_SIZE) == q->front);
}

void enqueue(QueueType *q, int n){
    if(is_full(q)){
        return;
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = n;
}

element dequeue(QueueType *q){
    if(is_empty(q)){
        return -1;
    }
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

element peek(QueueType* q)
{
    if (is_empty(q)) {
        return -1;
    }
    return q->queue[(q->front + 1) % MAX_QUEUE_SIZE];
}

void radix_sort(int list[], int n)
{
    QueueType queues[BUCKETS];
    int factor = 1;

    for (int b = 0; b < BUCKETS; b++) { // 큐들의 초기화
        init(&queues[b]);
    }

    for (int d = 0; d < DIGITS; d++) {
        for (int i = 0; i < n; i++) { // 데이터들을 자릿수에 따라 큐에 입력
            enqueue(&queues[(list[i]/factor)%10],list[i]);
        }

        int j = 0;
        for (int b = 0; b < BUCKETS; b++) { // 버켓에서 꺼내어 list로 합침
            while (!is_empty(&queues[b])){
                list[j++] = dequeue(&queues[b]);
            }
        }
        factor *= 10; // 그 다음 자릿수로 감
    }
}

int main(){
    int list[8] = { 28, 93, 39, 81, 62, 72, 38, 26 };
    printf("Before: ");
    for (int i = 0; i < 8; i++) {
        printf("%d ", list[i]);
    }
    printf("\n");

    radix_sort(list, 8);

    printf("After: ");
    for (int i = 0; i < 8;i++){
        printf("%d ", list[i]);
    }
    printf("\n");

    return 0;
}

기수 정렬의 분석

입력 리스트가 n개의 정수를 가지고 있으면, 내부 루프는 n번 반복
정수가 d개의 자릿수를 가지고 있으면, 외부 루프는 d번 반복
따라서, 시간복잡도 $O(d * n)$가짐, d(32비트 컴퓨터의 경우 대개 10개 정도의 자릿수만을 가지게 됨)는 n에 비해 아주 작은 수가 되므로 시간복잡도를 $O(n)$이라고 해도 상관 없음

기수 정렬 장점: 다른 정렬 방법에 비해 비교적 빠른 수행 시간 안에 정렬를 마침
기술 정렬 단점: 정렬에 사용되는 키 값이 숫자로 표현외어야만 적용 가능함, 그 외(실수, 한글, 한자)를 사용할 경우 매우 많음 버켓이 필요하게 되기 때문에 기술 정렬의 적용이 불가능

9.10 정렬 알고리즘 비교

알고리즘	최선	평균	최악
삽입 정렬	$O(n)$	$O(n^2)$	$O(n^2)$
선택 정렬	$O(n^2)$	$O(n^2)$	$O(n^2)$
버블 정렬	$O(n^2)$	$O(n^2)$	$O(n^2)$
셸 정렬	$O(n)$	$O(n^{1.5})$	$O(n^{1.5})$
퀵 정렬	$O(nlogn)$	$O(nlogn)$	$O(n^2)$
힙 정렬	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$
합병 정렬	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$
기수 정렬	$O(dn)$	$O(dn)$	$O(dn)$

정렬 알고리즘별 실험 경과 (정수: 60,000개)

알고리즘	실행 시간(단위: sec)
삽입 정렬	7.438
선택 정렬	10.842
버블 정렬	22.894
셸 정렬	0.056
퀵 정렬	0.014
힙 정렬	0.034
합병 정렬	0.026

9.11 정렬의 응용: 영어 사전을 위한 정렬

<프로그램 9.11.1> 영어 사전 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
#define MAX_WORD_SIZE 50
#define MAX_MEANING_SIZE 500
#define MAX_SIZE 1000

typedef struct {
    char word[MAX_WORD_SIZE];
    char meaning[MAX_MEANING_SIZE];
} element;

element list[MAX_SIZE]; // 구조체 배열 선언
int n;

// e1 > e2 1
// e1 == e2 0
// e1 < e2 -1
int compare(element e1, element e2)
{
    return strcmp(e1.word, e2.word);
}

// 퀵 정렬
int partition(element list[], int left, int right)
{
    element pivot = list[left];
    int low = left;
    int high = right + 1;
    element tmp;
    do {
        do {
            low++;
        } while (low <= right && compare(list[low], pivot) < 0);

        do {
            high--;
        } while (high >= left && compare(list[high], pivot) > 0);

        if (low < high) {
            SWAP(list[low], list[high], tmp);
        }
    } while (low < high);

    SWAP(list[left], list[high], tmp);
    return high;
}

void quick_sort(element list[], int left, int right)
{
    if (left < right) {
        int q = partition(list, left, right);
        quick_sort(list, left, q - 1);
        quick_sort(list, q + 1, right);
    }
}

void help()
{
    printf("****************\n");
    printf("i: input\n");
    printf("s: sort\n");
    printf("p: printf\n");
    printf("q: quit\n");
    printf("****************\n");
}

void insert(element e)
{
    if (n < (MAX_SIZE - 1)) {
        list[n++] = e;
    }
}

void print()
{
    for (int i = 0; i < n; i++) {
        printf("%s: %s\n", list[i].word, list[i].meaning);
    }
}

int main()
{
    element e;
    char command;
    do {
        help();
        command = getchar();
        fflush(stdin);
        switch (command) {
        case 'i':
            printf("Word: ");
            gets(e.word);
            printf("Meaning: ");
            gets(e.meaning);
            insert(e);
            break;
        case 's':
            quick_sort(list, 0, n - 1);
            break;
        case 'p':
            print();
            break;
        }
    } while (command != 'q');
}

<참고자료>
천인국 · 공용해 · 하상호 지음,『C언어로 쉽게 풀어쓴 자료구조』, 생능출판(2016)