20장 알고리즘

20.1 검색

검석(Search)이란 자료의 집합(table)에서 원하는 어떤 자료(Key)가 있는지, 있다면 어디에 있는지를 찾아내는 알고리즘이다.

검색은 소프트웨어 공학에서 가장 오랫동안 연구되어 온 주제이며 또한 가장 실용적인 주제이기도 하다. 원하는 자료를 빠르게 찾는 것뿐만 아니라 새로 추가되거나 삭제되는 자료들도 다음 검색을 위해 어떻게 조작할 것인지까지 포괄하는 종합 자료 관리 알고리즘이 바로 검색이다.

20.1.1 순차 검색

순차 검색(Sequential Search)은 모든 알고리즘 중에서 가장 기본적이면서 상식적인 검색 방법이다. 테이블을 처음부터 순서대로 읽으면서 원하는 키와 비교하기를 검색에 성공하거나 아니면 테이블 끝에 이를 때까지 반복하는 것이다. 임의의 자료에도 적용할 수 있으며 자료를 별도로 관리할 필요도 없지만 효율은 별로 좋지 못하다.

• 예제 SequentailSearch

#include <stdio.h>     int LinearSearch(int *ar, unsigned num, int key) { unsigned i;     for ( i = 0 ; i < num ; i++ ) { if( ar[i] == key ) { return i ; } } return -1; }     void main() { int ar[] = { 23, 27, 19, 34, 435, 345, 2432, 1233, 250, 11 } ; unsigned num; int key, idx;     num = sizeof(ar) / sizeof(ar[0]); key = 1233; idx = LinearSearch(ar, num, key); if( idx == -1 ) { puts("찾는 값이 없음"); } else { printf("찾는 값이 %d번째 있음\n",idx); } }

키는 보통 테이블에서 다른 레코드와 중복되지 않는 유일한 값을 가지는 것을 사용하는데 예를 들어 주소록 구조체 배열이라면 주민등록번호를 키로 사용하는 것이 가장 좋다. 이처럼 레코드 간에 중복되지 않느 유일한 키를 피라이머리 키(Primary Key)라고 한다. 특정 키와 일치하는 레코드가 둘 이상 존재한다면 처음부터 검색을 시작하여 실패할 때까지 반복 검색하여 모든 레코드를 찾을 수 있다.

C++ 제공 순차 검색 함수

void *lsearch( const void *key, void *base, unsigned int *num, unsigned int width, int (__cdecl *compare)(const void *elem1, const void *elem2) );

인수로 키값, 테이블의 선두 번지, 요소의 개수와 크기, 비교 함수에 대한 함수 포인터를 요구한다. 임의의 타입에 대해 동작해야 하므로 비교 방법을 사용자가 함수로 직접 정의할 수 있도록 되어 있다.

• 예제 lsearch

#include <stdio.h> #include <search.h>     int compare( const void *elem1, const void *elem2 ) { return (*(int*)elem1 != *(int*)elem2); }     void main() { int ar[] = { 23, 47, 19, 63, 57, 26, 75, 73, 82, 89, 47, 11 }; unsigned num; int key; int *ptr;     num = sizeof(ar) / sizeof(ar[0]); key = 75; ptr = (int*)lsearch(&key, ar, &num, sizeof(int), compare); if( ptr == NULL ) { puts("찾을 값이 없습니다."); } else { printf("찾는 값은 %d번째 있습니다.\n", ptr-ar); } }

20.1.2 이분 검색

이분 검색은 구간의 중간값과 키값의 대소를 구분하여 테이블을 절반씩 나눠 가며 비교하는 방법이다. 순차 검색이 상등 비교만 하고 순서대로 검색하는데 비해 이분 검색은 대소 비교를 통해 구간을 나눠 비교하는 좀 더 지능적인 방법이라고 할 수 있다. 한 번 비교할 때마다 테이블의 길이가 절반씩 줄어들기 때문에 검색 효율은 아주 좋으며 테이블이 웬만큼 커도 느려지지 않는다.

이분 검색이 가능하려면 테이블의 모든 자료가 오름차순으로 정렬되어 있어야 한다는 제약이 있다.

• 예제 BinarySearch

#include <stdio.h>     int BinarySearch(int *ar, unsigned num, int key) { unsigned upper, lower, mid;     lower = 0 ; upper = num-1; for( ;; ) { mid = (upper+lower)/2;     if( ar[mid] == key) return mid; if( ar[mid] > key ) { upper = mid - 1; } else { lower = mid + 1; }     if( upper < lower ) { return -1; } } }     void main() { int ar[] = {2,6,13,19,21,22,23,29,35,48,62,89,90,95,99,102,109,208,629}; unsigned num; int key, idx;     num = sizeof(ar) / sizeof(ar[0]); key = 29; idx = BinarySearch(ar, num, key); if( idx == -1 ) { puts("찾는 값이 없습니다."); } else { printf("찾는 값은 %d번째 \n", idx); } }

이분 검색은 범위를 계속 절반씩 줄여 가면서 검색하기 때문에 테이블이 커도 비교 회수가 많지 않은 장점이 있다. 배열의 크기가 n일때 최악의 경우 log₂n번 비교하면서 원하는 값을 찾을 수 있다. n이 40억이라도 32번만 비교하면 찾을 수 있다. 이분검색이 이렇게 빠른 이유는 자료가 크기순으로 정렬되어 있기 때문이다.

C표준 이분 검색 함수

void *bsearch( const void *key, const void *base, size_t num, size_t width, int (__cdecl *comapre)(const void *elem1, const void *elem2) );

key는 찾고자 하는 값, base는 배열 선두 번지, num은 요소 개수, width는 요소의 크기, compare는 사용자가 지정하는 비교함수인데 비교 대상이 되는 두 개의 값을 전달한다.

• 예제 bsearch

#include <stdio.h> #include <search.h>     int compare( const void *elem1, const void *elem2 ) { return (*(int*)elem1 - *(int*)elem2); }     void main() { int ar[] = {2,6,13,19,21,22,23,29,35,48,62,89,90,95,99,102,109,208,629}; unsigned num; int key; int *ptr;     num = sizeof(ar) / sizeof(ar[0]); key = 29; ptr = (int*)bsearch(&key, ar, num, sizeof(int), compare); if( ptr == NULL ) { puts("찾는 값이 없습니다."); } else { printf("찾는 값은 %d번째 \n", ptr-ar); } }

compare 함수는 두 정수의 대소 관계를 비교해 두 값의 차를 리턴한다. 문자열을 비교한다면 strcmp(i)함수로 비교한 값을 리턴하면 된다.

bsearch 함수는 어셈블리로 작성되어 있고 고도로 최적화되어 있으므로 훨씬 더 빠르고 안정적이다.

좀 더 발전된 이분 검색 방법으로 피보나치 수열을 사용하거나 보간을 하는 방법이 있다. 이 방법들은 범위를 줄일 때 키가 없다고 판단된느 부분을 빠르게 건너뜀으로써 단순 이분 검색에 비해서는 속도가 조금 더 빠르다.

이분 검색은 중간 부분을 빠르게 액세스할 수 있어야 하므로 배열에 대해서만 사용할 수 있다.

20.1.3 해시

해시(Hash)는 자료를 입력할 때부터 검색하기 쉬운 위치에 삽입하는 방법이다. 따라서 해시는 검색 방법이라기보다는 빠르 ㄴ검색을 위해 자료를 관리하는 기법이라고 볼 수 있다.

자료가 저장되는 전체 저장소를 해시 테이블(Hash Table)이라고 ㅏㄴ다. 해시 테이블은 여러 개의 버킷(Bucket)으로 나누어진다. 데이터를 삽입할 때 데이터의 값으로부터 적절한 버킷을 선택해서 삽입해야 한다. 버킷은 또한 여러 개의 슬롯(Slot)으로 구성되는데 슬롯은 버킷에 데이터가 저장되는 단위이다.

해싱의 가장 기초적인 연산은 자료가 새로 입력될 때 이 자료를 어떤 버킷에 넣을지를 결정하는 것인데 이연산을 하는 함수를 해시 함수라고 한다. 해시 함수는 입력된 키값으로 버킷의 번호(해시값)를 찾아내는 함수인데 새로 자료를 삽입할 때 해시 함수가 리턴하는 버킷 번호에 자료를 삽입한다.

• 예제 Hashing

#include <stdio.h> #include <memory.h>     #define BK 10 #define SL 1 int hashtable[BK][SL];     int hash(int key) { return key % 10; }     void AddKey( int key ) { int bucket;     bucket = hash(key); if( hashtable[bucket][0] == 0 ) { hashtable[bucket][0] = key; } }     bool FindKey(int key) { int bucket;     bucket = hash(key); return (hashtable[bucket][0] == key); }     void main() { int i, key;     memset(hashtable, 0, sizeof(hashtable)); for( i = 0 ; i < 5 ; i++ ) { printf("%d.번째 값을 입력 : ", i+1); scanf("%d", &key); AddKey(key); } printf("검색할 키를 입력 : "); scanf("%d", &key); if( FindKey(key) ) { puts("검색됨"); } else { puts("없음"); } }

해시 함수 hash는 키의 마지막 자리 수 하나만으로 해시값을 계산하고 있다. 10으로 나눈 나머지를 해시값으로 선택하므로 버킷은 10개를 준비하면 된다. 그래서 해시 테이블의 버킷 수는 10으로 정의했으며 충돌 현상을 쉽게 관찰하기 위해 슬롯은 1로 정의해두었다.

AddKey 함수는 입력된 키로부터 hash 함수를 호출하여 해시값을 찾고 이 버킷이 비어 있을 때 해시 테이블에 데이터를 추가한다. 만약 이미 버킷이 점령되어 있다면 값을 추가 할 수 없다.

다섯 개의 값을 입력했는데 각 입력에 의해 AddKey함수는 뒷자리 번호에 해당하는 버킷에 값을 저장한다.

해시 테이블이 아무리 크고 데이터가 많다 하더라도 검색 시간은 상수로 항상 일정하다. 검색 시간만으로 본다면 해시는 모든 검색 알고리즘 중에 가장 빠르다.

그러나 해싱의 가장 큰 문제점은 버킷끼리 충돌할 수 있다는 점이다. 새로 삽입하고자 하는 키의 버킷이 이미 점령되어 있다면 이 키는 해시 테이블에 추가할 수 없다. 버킷이 이미 점령되어 값을 추가할 수 없는 상황을 충돌(Collision)이라고 한다.

이 충돌을 어떻게 해결할 것인가가 해싱의 관건이며 다수의 해결 방법이 있다

   

:: 다중 슬롯

슬롯을 충분히 크게 잡기만 해도 충돌을 많이 완화시킬 수 있다. 충돌이 발생허다라도 버킷의 슬롯이 많아지면 다음 슬롯에 데이터를 저장할 수 있으므로 슬롯 크기를 초과하는 데이터가 입력될 때만 문제가 발생한다. 슬롯 크기를 늘리면 데이터를 추가 및 검색하는 함수도 다중 슬롯을 지원하도록 수정해야 한다.

• 예제 MultiSlot

#include <stdio.h> #include <memory.h>     #define BK 10 #define SL 3 int hashtable[BK][SL];     int hash(int key) { return key % 10; }     void AddKey( int key ) { int i; int bucket;     bucket = hash(key); for ( i = 0 ; i < SL ; i++ ) { if( hashtable[bucket][i] == 0 ) { hashtable[bucket][i] = key; break; } } }     bool FindKey(int key) { int i; int bucket;     bucket = hash(key); for ( i = 0 ; i < SL ; i++ ) { if( hashtable[bucket][i] == key ) { return true; } } return false; }     void main() { int i, key;     memset(hashtable, 0, sizeof(hashtable)); for( i = 0 ; i < 5 ; i++ ) { printf("%d.번째 값을 입력 : ", i+1); scanf("%d", &key); AddKey(key); } printf("검색할 키를 입력 : "); scanf("%d", &key); if( FindKey(key) ) { puts("검색됨"); } else { puts("없음"); } }

단 빈 슬롯이 하나도 없다면 이때는 삽입에 실패하여 여전히 충돌이 발생한다. 그래서 다중 슬롯은 충돌을 지연시키기는 해도 완벽하게 해결하지는 못한다. 게다가 슬롯이 많아지면 추가, 검색 함수가 복잡해지기 때문에 실제 해싱을 할 때 슬롯은 하나만 쓰고 다른 방법을 사용하는 것이 더 일반적이다.

   

:: 정교한 해시 함수

해시 테이블이 아무리 커도 충돌은 발생할 수 있는데 이 충돌을 가급적 늦추고 버킷을 골고루 사용하려면 키로부터 해시값을 찾는 해시 함수가 정교해야 한다.

바람직한 해시 함수는 입력되는 임의의 값으로부터 균일한 해시값을 만들어 내야 한다. 또한 삽입과 검색 소도에 직접적인 영향을 미치므로 너무 복잡해서도 안되며 해시값을 신속하게 계산할 수 있어야 한다. 해시 함수를 만드는 여러 가지 연산 방법들이 개발되어 있는데 입력값을 제곱한다거나 쉬프트, 비트 연산으로 일부 비트만 취하는 간단한 방법에서부터 인력되는 값들의 분산, 표준 편차 등을 활용하는 수학적인 방법도 있다.

모든 경우에 대해 잘 동작하는 그런 해시 함수는 없다. 저장하는 값의 성질을 잘 분석한 후에 값들을 골고루 분산시킬 수 있는 해시 함수를 찾아야 한다. 정교한 해시 함수는 충돌을 최소화하고 기억 장소를 효율적으로 사용하는 방법 중 하나이기는 하지만 충돌을 근본적으로 해결하지는 못한다.

   

:: 선형 탐색

슬롯이 넉넉하고 해시 함수가 정교해도 충돌은 언제나 발생할 가능성이 있다. 그래서 충돌이 발생할 때의 대처 상황을 정의해야 하는데 선형 탐색법이 그 중 가장 간단한 방법이다. 선형 탐색법(Linear Probing)은 충돌이 발생할 경우 이 데이터를 버리지 않고 다른 버킷에라도 대신 집어넣는 방법이다.

• 예제 LinearProbe

#include <stdio.h> #include <memory.h>     #define BK 10 #define SL 1 int hashtable[BK][SL];     int hash(int key) { return key % 10; }     void AddKey( int key ) { int bucket;     bucket = hash(key); while( hashtable[bucket][0] != 0 ) { bucket = bucket+1 % BK; } hashtable[bucket][0] = key; }     bool FindKey(int key) { int bucket;     bucket = hash(key); while( hashtable[bucket][0] != 0 ) { if( hashtable[bucket][0] == key ) return true; bucket = bucket+1 % BK; } return false; }     void main() { int i, key;     memset(hashtable, 0, sizeof(hashtable)); for( i = 0 ; i < 5 ; i++ ) { printf("%d.번째 값을 입력 : ", i+1); scanf("%d", &key); AddKey(key); } printf("검색할 키를 입력 : "); scanf("%d", &key); if( FindKey(key) ) { puts("검색됨"); } else { puts("없음"); } }

입력된 데이터의 버킷 번호를 조사하여 데이터를 넣되 만약 비어있지 않다면 다음 버킷을 조사한다. 다음 버킷도 비어있지 않다면 그 다음 빈 버킷을 계속해서 찾아 최초로 빈 버킷에 값을 써넣는다.

만약 빈 칸이 하나도 없다면 무한 루프에 빠지기 때문에 최초 버킷을 기억 했다가 이 자리를 기억했다가 이 자리로 다시 돌아왔을 때 에러 처리함으로써 해결할 수 있다. 그러나 무한루프만 해결했을 뿐이지 데이터 삽입은 실패하므로 해시 테이블을 더 크게 만들거나 해시 테이블보다 더 많은 자료를 삽입하지 않도록 하는 것이 근본적으로 옳다.

선형 탐색법은 삭제에 무척 취약한 알고리즘인데 FindKey가 빈칸을 찾을 때까지 검색을 하도록 되어 있어 삭제할 때 빈칸으로 만들어서는 안된다. 삭제할 때는 -1 등의 특이값으로 삭제된 칸임을 명시하고 FindKey는 삭제된 칸 이후 계속 검색하도록 해야한다.

   

:: 재해시

재해시도 선형 탐색법과 유사한 방법이다. 재해시는 대체 칸을 찾는 대신 해시 함술르 별도로 하나 더 두는 방법이다.

• 예제 ReHash

#include <stdio.h> #include <memory.h>     #define BK 10 #define SL 1 int hashtable[BK][SL];     int hash(int key) { return key % 10; } int hash2(int key) { return (key/10 + key%10) % 10; }     void AddKey( int key ) { int bucket;     bucket = hash(key); if( hashtable[bucket][0] != 0 ) { bucket = hash2(key); } if( hashtable[bucket][0] == 0 ) { hashtable[bucket][0] = key; } }     bool FindKey(int key) { int bucket;     bucket = hash(key); if( hashtable[bucket][0] == key ) { return true; } bucket = hash2(key); if( hashtable[bucket][0] == key ) { return true; } return false; }     void main() { int i, key;     memset(hashtable, 0, sizeof(hashtable)); for( i = 0 ; i < 5 ; i++ ) { printf("%d.번째 값을 입력 : ", i+1); scanf("%d", &key); AddKey(key); } printf("검색할 키를 입력 : "); scanf("%d", &key); if( FindKey(key) ) { puts("검색됨"); } else { puts("없음"); } }

hash2라는 함수를 하나 더 정의하고 있는데 이 함수는 일자리와 십자리수를 더 한값을 10으로 나누기 연산해서 버킷을 찾는다.

   

:: 동적 슬롯

동적 슬롯은 슬롯의 개수를 가변적으로 관리하는 방법이다. 선형 탐사나 재해시가 충돌을 회피하는 방법이라면 동적 슬롯은 충돌에 적극적으로 대처하는 방법이라고 할 수 있다. 최초 일정한 크기의 슬롯을 준비하되 버킷이 가득 찰 정도로 데이터가 들어온다면 슬롯 크기를 실행 중에 늘린다. 이렇게 하면 대체 버킷을 찾을 필요도 없고 삭제하는 방법도 번거롭지 않다.

슬롯은 실행 중에 크기를 늘릴 수 있어야 하므로 동적 배열이나 연결리스트로 작성한다. 버킷 내에서의 검색은 순차 검색을 사용하되 슬롯의 크기가 무척 커질 수 있다면 이분 검색을 쓰는 것이 유리할 것이다.

20.2 정렬

정렬(Sort)이란 임의의 자료 집합을 일정한 기준에 따라 나열하는 것이다. 작은 것을 먼저 나열하는 것을 오름차순(Ascending)정렬이라고 하고 큰 것을 먼저 나열하는 것을 내림차순(Descending) 정렬이라고 한다. 이때 크기라는 기준은 자료의 형태에 따라 다른데 수치라면 값이 큰 수를 크다고 판단하며 문자열은 문자 코드의 순서로 대소를 판단한다.

정렬 대상은 보통 레코드라고 불리는 구조체인데 구조체의 멤버 중에 정렬의 기준이 되는 멤버를 키(Key)라고 한다.

정렬의 원리는 간단하다. 레코드의 키들을 비교해보고 순서를 바꿀 필요가 있는 레코드를 정렬이 완료될 때까지 반복하는 것이다. 알고리즘별로 메모리의 사용량과 정렬 속도, 정렬 방법의 복잡성이 다르고 자료의 양과 효율의 비례관계가 다르다. 따라서 모든 경우에 적합한 최적의 알고리즘은 없으며 자료의 형태와 용도에 맞는 알고리즘을 선택해야 한다.

20.2.1 버블 정렬

• 예제 BubbleSort

#include <stdio.h> #include <string.h>     #define SWAP(a,b) { int t; t = a; a = b; b = t; }     void BubbleSort(char* ar, int num) { int i, j;     for( i = 0 ; i < num ; i++ ) { for( j = 1 ; j < num-1 ; j++ ) { if( ar[j-1] > ar[j] ) { SWAP(ar[j-1], ar[j]); } } } }     void main() { char str[] = "winapi";     printf("정렬 전의 문자열 %s\n",str); BubbleSort(str, strlen(str)); printf("정렬 후의 문자열%s\n", str); }

BubbleSort 함수는 두 개의 루프로 구성되어 있는데 i루프는 문자열 선두에서부터 뒤로 이동하고 j루프는 매 i에 대해 num-i까지 비교 및 교환을 반복한다.

버블 정렬은 이런식으로 제일 큰 값을 뒤로 계속 보내되 중간의 인접 레코드도 대충 교환해 둔다. 그러나 버블정렬은 알고리즘이 너무 간단해서 정렬 속도는 좋지 못하다. 비교와 교환을 너무 자주 하기 때문에 정렬 중에 이미 정렬이 완료되는 경우도 있다. 이런 경우는 교환 플래그를 사용하여 약간의 시간 절약을 할 수 있다.

void BubbleSort2( char *ar, int num ) { int i, j; bool bChange;     for( i = 0 ; i < num-1 ; i++ ) { bChange = false; for( j = 1 ; j < num-i ; j++ ) { if( ar[j-1] > ar[j] ) { SWAAP(ar[j-1], ar[j] ); bChange = true; } } if( bChange == false ) break; } }

bChange라는 지역변수를 선언하고 j루프에 들어가기 전에 이 값을 false로 설정한 후 값을 교환할 때 true로 변경한다. 만약 j루프가 끝난 후 bChange가 false값을 유지하고 있다면 한 번도 교환이 일어나지 않았으므로 이때 정렬이 완료된 것으로 판단하여 i 루프를 탈출한다.

20.2.2 선택 정렬

가장 단순한 정렬 방법인 선택 정렬은 최소값을 찾아 앞쪽으로 이동하기를 배열 크기만큼 반복하는 정렬 방법이다. 배열에서 제일 작은 값을 찾아 처음으로 보낸다. 그리고 첫 번째 요소는 제외하고 남은 요소들 중에 제일 작은 값을 다시 찾아 선두로 보내기를 배열 끝까지 반복한다.

• 예제 SelectionSort

#include <stdio.h> #include <string.h>     #define SWAP(a,b) { int t; t = a; a = b; b = t; }     void SelectSort(char *ar, int num) { int minidx; int i, j;     // 배열 전체 순회 for ( i = 0 ; i < num-1 ; i++ ) { // i이 후의 최소값을 찾는다 for ( minidx = i, j = i+1 ; j < num ; j++ ) { if(ar[minidx] > ar[j] ) { minidx = j ; } }     // 최소값을 현재항과 교환 if( minidx != i ) { SWAP(ar[minidx], ar[i]); } } } void main() { char str[] = "winapi";     printf("정렬 전의 문자열 %s\n",str); SelectSort(str, strlen(str)); printf("정렬 후의 문자열%s\n", str); }

선택 정렬은 작은 값을 선택하기 위해 비교를 여러 번 하지만 교환 회수가 작은 것이 장점이다. 최악의 경우라고 하더라도 레코드의 개수만큼만 교환이 발생하므로 교환 비용이 비싼 구조체 배열 등에 적합하다.

20.2.3 삽입 정렬

삽입 정렬은 배열의 앞쪽부터 순회하면서 정렬해 오는데 앞쪽의 정렬된 부분에서 대상 레코드의 위치를 찾아서 삽입하는 알고리즘이다. 자기보다 더 큰 값을 계속 뒤로 보내면서 빈 칸 하나를 만든 후 자신보다 작거나 같은 값을 만날 때 그 오른쪽 위치에 삽입한다.

• 예제 InsertionSort

#include <stdio.h> #include <string.h>     #define SWAP(a,b) { int t; t = a; a = b; b = t; }     void InsertSort(char *ar, int num ) { int i, j; char temp;     // 두번째 요소부터 끝까지 순회 for( i = 1 ; i < num ; i++ ) { // 앞쪽으로 이동하면서 자기보다 큰 값을 한 칸씩 오른쪽으로 이동 for( temp = ar[i], j = i ; j >= 0 ; j-- ) { if( ar[j-1] > temp ) { ar[j] = ar[j-1]; } else { break; } } // 자기보다 크지 않은 최초의 칸 자리에 자신을 삽입 ar[j] = temp; } }     void main() { char str[] = "winapi";     printf("정렬 전의 문자열 %s\n",str); InsertSort(str, strlen(str)); printf("정렬 후의 문자열%s\n", str); }

i루프로 배열 끝까지 순회하되 두 번째 요소부터 시작한다. 왜냐하면 앞쪽의 한 문자만 보면 이 부분 문자열은 이미 정렬되어 있다고 볼 수 있기 때문이다. j루프는 ar[i] 문자(temp)와 바로 앞쪽의 문자를 비교하여 왼쪽이 더 클 경우 이 값을 오른쪽으로 한 칸 이동시킨다. 자기보다 더 큰 값을 계속 이동시키다가 크지 않은 값을 만나면 이 값 다음 자리에 ar[i]에 삽입한다.

   

i가 4일 때

먼저 temp에 ar[i]의 값을 복사해 둔다. 그리고 j를 i부터 배열 앞쪽으로 이동시키면서 왼쪽 요소와 비교하는데 첫 번째 루프에서 p가 l보다 크므로 p를 오른쪽의 l자리로 이동시킨다.

이런 식으로 앞쪽의 부분 문자열에서 자기보다 더 큰 값을 계속 뒤쪽으로 이동시키며 자신이 들어갈 자리를 찾아 삽입되는 것이다.

삽입 정렬 속도를 개선하는 여러 가지 방법들이 연구되어 있는데 배열의 제일 첫 요소에 가장 작은 값을 미리 배치하거나 아니면 충분히 작은 더미값을 배치하여 j가 배열 범위를 벗어나지 않도록 하는 방법이 있다. 또 배열의 앞쪽은 항상 정렬되어 있으므로 새로운 값이 삽입될 때 위치를 이분 검색으로 찾아 일괄적으로 배열 요소를 이동하는 방법이 사용되기도 한다.

쉘 정렬(Shell Sort)은 삽입 정렬을 개선한 좀 빠른 알고리즘이다. 삽입 정렬은 인접 요소끼리 비교하여 자리를 이동하는데 비해 쉘 정렬은 일정수만큼 건너뛰면서 비교하여 교환하는 알고리즘이다. 이때 몇 칸씩 건너뛸 것인가에 따라 구현이 조금씩 달라지는데 임의의 데이터에 대해서도 항상 제 속도가 나와 퀵 정렬만큼이나 빠르다.

20.2.4 퀵 정렬

퀵 정렬(Quick Sort)은 이름 그대로 속도가 대단히 빠른 정렬 알고리즘이다. 큰 배열을 일정한 기준값을 경계로 하여 기준값보다 큰 값들과 작은 값들로 구성된 작은 두개의 배열로 분할한다. 그리고 분할된 각 배열을 똑같은 방법으로 다시 정렬하는 점진적인 방법을 사용한다.

• 예제 QuickSort

#include <stdio.h> #include <string.h>     #define SWAP(a,b) { int t; t = a; a = b; b = t; }     void QuickSort( char *ar, int num ) { int left, right; char key;     // 구간이 1이면 정렬 끝 if( num <= 1 ) return;     // 기준 값 결정 : 배열상의 제일 끝 요소 key = ar[num-1]; for( left = 0, right = num-2 ;; left++, right-- ) { while( ar[left] < key ) { left++; } while( ar[right] > key ) { right--; } if( left >= right ) break;                // 좌우가 만나면 끝 SWAP(ar[left], ar[right]); } SWAP(ar[left], ar[num-1]);                // 기준값과 i위치의 값 교환     QuickSort(ar, left);                        // 왼쪽 구간 정렬 QuickSort(ar+left+1, num-left-1);        // 오른쪽 구간 정렬 } void main() { char str[] = "winapi";     printf("정렬 전의 문자열 %s\n",str); QuickSort(str, strlen(str)); printf("정렬 후의 문자열%s\n", str); }

큰 배열을 분할하기 위해 먼저 기준값을 선정하는데 배열 선두나 마지막 기준값으로 사용하는 것이 가장 쉽다. 그리고 for 루프에서 배열의 왼쪽과 오른쪽에 각각 left, right 포인터를 두고 중앙으로 이동하면서 left에 기준값보다 큰 값, right에 기준값보다 작은 값을 찾는다. 그리고 두 값을 교환하여 기준값보다 작은 값은 배열의 왼쪽으로 보내고 큰 값은 오른쪽으로 보낸다.

이 과정을 left와 right가 만날 때까지 반복하는데 이때 left는 기준값보다 큰 값을 가리킨다. left와 기준값을 교환하여 left가 가리키는 값을 배열 끝으로 보내면 기준 값의 왼쪽에는 이 값보다 작은 값만 있고 오른쪽에는 더 큰 값만 있을 것이다. 기준값이 있는 위치의 왼쪽 구간과 오른쪽 구간을 똑같은 방법으로 정렬하되 구간 크기가 1이 될 때까지 이 과정을 반복하면 전체 배열이 정렬된다.

퀵 정렬의 성능은 기준값을 어떻게 설정하는가에 따라 결정되는데 기준값이 중간값에 가까울수록 좌우 구간이 균일하게 분할되어 더 빨리 정렬할 수 있다. 이 예제에서는 배열의 제일 끝값을 취했기 때문에 운에 따라 기준값이 결정되며 이미 정렬되어 있을 경우 항상 큰 값이 선택되어 왼쪽 구간만 커지는 문제가 있다. 그래서 기준값을 난수로 선택하여 한쪽으로 치우침을 방지하거나 아니면 적절한 중간값을 취하는 방법을 쓰기도 한다.

또 재귀 호출을 하기 때문에 배열이 아주 클 경우 스택 오버플로우가 발생할 위험이 있는데 이럴 때는 자체 스택을 만들어 비재귀하는 방식으로 개선할 수 있다. 아니면 구간이 아주 작을 때는 더 이상 재귀 호출을 하지 말고 선택 정렬이나 삽입 정렬 같은 좀 더 간단한 알고리즘을 사용하는 방법도 흔히 사용된다.

C표준 라이브러리 qsort

• 예제 qsort

#include <stdio.h> #include <algorithm>     int compare( const void *a, const void *b ) { if( *(char*)a == *(char*)b ) return 0; if( *(char*)a > *(char*)b ) return 1;     return -1; }     void main() { char str[] = "greathuman";     printf("정렬 전의 문자열 : %s\n", str); qsort(str, strlen(str), sizeof(char), compare); printf("정렬 후의 문자열 : %s\n", str); }