20-2.정렬

20-2-가.버블 정렬

정렬(Sort)이란 임의의 자료 집합을 일정한 기준에 따라 나열하는 것이다. 보통 자료의 크기순으로 나열하는데 작은 것을 먼저 나열하는 것을 오름차순(Ascending) 정렬이라고 하고 큰 것을 먼저 나열하는 것을 내림차순(Descending) 정렬이라고 한다. 이때 크기라는 기준은 자료의 형태에 따라 다른데 수치라면 값이 큰 수를 크다고 판단하며 문자열은 문자 코드의 순서로 대소를 판단한다. 문자열 형태로 된 수치나 코드값 등은 자료의 구조에 따라 대소를 판별하는 방법이 달라진다. 예를 들어 직위로 정렬할 때는 사장, 상무, 부장, 과장, 대리, 사원 순의 미리 정한 순서대로 정렬한다.

정렬은 굉장히 오랫동안 연구되어 왔고 지금도 연구중인 알고리즘의 하나인데 역사가 오래된만큼 개발되어 있는 알고리즘의 수도 상당히 많다. 실제 문제에 바로 사용할 수 있는 알고리즘이 적어도 수십개 정도 있는데 이 많은 정렬 알고리즘을 일일이 다 연구할 필요는 없다. 쓸만한 알고리즘 몇 개만 알아도 되고 아니면 표준 정렬 함수만 활용해도 정렬 기능을 쓸 수 있다. 또한 현대적인 윈도우즈 환경에서는 컨트롤들이 자동화된 정렬 기능을 제공하므로 별도로 정렬해야 할 경우도 적다.

그림은 탐색기의 파일 목록을 표시하는 리스트 뷰 컨트롤인데 알파벳순으로 파일을 정렬하여 보여준다. 그러나 정렬은 학술적으로 중요한 의미를 가지는데 특수한 경우를 위한 최적화된 정렬을 해야 할 경우 이미 작성된 정렬 알고리즘을 바탕으로 해야 한다. 또한 더 고급한 알고리즘을 연구하거나 직접 만들어야 할 때 정렬 알고리즘의 기법들 중 일부를 재활용할 수 있을 것이다.

정렬 대상은 보통 레코드라고 불리는 구조체인데 구조체의 멤버 중에 정렬의 기준이 되는 멤버를 키(Key)라고 한다. 정렬 알고리즘은 레코드의 키를 비교한 후 레코드를 통째로 정렬하는데 키는 정렬할 때마다 다르게 줄 수 있다. 예를 들어 주소록 데이터의 경우 이름을 키로 하여 정렬할 수도 있고 나이순으로 정렬할 수도 있다. 만약 대소가 같은 레코드가 둘 이상 있다면 이 레코드들을 정렬하는 별도의 이차키를 사용하기도 한다.

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

정렬 알고리즘은 여러 가지 방법으로 분류할 수 있는데 메모리 내부에서만 정렬하는가 아니면 디스크의 자료를 정렬하는가에 따라 내부 정렬과 외부 정렬로 나누기도 하고 레코드를 직접 교환하는가 아니면 레코드에 대한 포인터만 교환하는가에 따라 직접 정렬과 간접 정렬로 나누기도 한다. 그리고 각 정렬 알고리즘은 같은 순서의 레코드가 정렬 후에도 순서를 유지하는가에 따라 안정성(Stability)의 여부가 다르다.

여기서는 학술적으로 의미를 가지는 알고리즘과 실제 많이 사용하는 알고리즘 4가지만 구현해 보기로 한다. 먼저 간단한 정렬 알고리즘인 버블 정렬부터 시작해 보자. 버블 정렬은 레코드의 선두부터 인접 요소를 비교하여 큰 값을 뒤로 보내는 방식으로 정렬하는데 이 과정을 끝까지 반복하면 모든 레코드가 정렬된다. 예제를 보자.

예 제 : BubbleSort

#include <Turboc.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-1;i++) {

for (j=1;j<num-i;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);

}

winapi라는 짧은 문자열을 정렬한다. main에서 이 문자열과 길이를 알려 주면 BubbleSort 함수가 문자열을 정렬한다.

정렬 전의 문자열 : winapi

정렬된 문자열 : aiinpw

BubbleSort 함수는 두 개의 루프로 구성되어 있는데 i루프는 문자열 선두에서부터 뒤로 이동하고 j루프는 매 i에 대해 num-i까지 비교 및 교환을 반복한다. 버블 정렬이 레코드를 정렬하는 과정을 그림으로 그려 보면 다음과 같다.

왼쪽 그림은 i가 0일 때 j루프의 동작이다. j는 1부터 문자열 끝까지 이동하면 j번째 자리의 레코드와 바로 왼쪽의 레코드를 비교하여 왼쪽이 더 크다면 두 값을 교환하여 큰 값을 뒤로 보낸다. 최초 j가 1일 때 ar[1]의 i와 ar[0]의 w를 비교하는데 w가 더 크므로 두 레코드를 교환하여 iw로 만든다. 다음 j루프에서 계속 두 레코드를 비교하여 w를 뒤쪽으로 연속적으로 이동시키는데 j루프가 끝나면 제일 큰 레코드가 가장 뒤쪽으로 이동되어 마지막 레코드의 정렬이 완료된다.

다음 i 루프에서 배열 처음부터 이 과정을 반복하되 마지막 레코드는 정렬되었으므로 더 이상 정렬할 필요가 없다. 그래서 j루프는 num-i까지만 반복하도록 했다. i가 1일 때 j는 뒤쪽으로 이동하며 n과 a를 교환하고 p와 i를 교환한다. n과 a가 교환된 직후에 n과 p도 비교되는데 이때는 p가 더 크므로 두 레코드를 교환하지 않는다. i가 1일 때의 루프에서 남은 문자중 제일 큰 p가 다시 제일 뒤쪽으로 이동한다. 버블 정렬은 이런 식으로 제일 큰 값을 뒤로 계속 보내되 중간의 인접 레코드도 대충 교환해 둔다.

i가 2일 때 j는 다시 배열 처음부터 순회하면서 i와 a를 교환하고 n과 i를 교환하여 n을 제일 뒤로 보낸다. i가 3일 때는 더 이상 바꿀 레코드가 없으므로 이 단계에서 정렬이 완료된다. 비교와 교환에 의해 작은 레코드는 배열 앞쪽에 모이고 큰 레코드는 뒤쪽으로 이동한다.

버블 정렬은 두 값을 비교할 때 왼쪽이 더 큰 경우만 교환하므로 같은 크기의 레코드는 원래의 순서를 유지하는 특성이 있다. 위 예에서 두 개의 i가 있는데 정렬된 후에도 두 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]) {

SWAP(ar[j-1],ar[j]);

bChange=TRUE;

}

}

if (bChange==FALSE) break;

}

}

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

플래그를 사용하면 비교 회수를 줄일 수 있다는 장점이 있지만 플래그 값을 대입하는 것도 시간이 들기 때문에 꼭 이 방법이 빠르다고만은 할 수 없다. 루프 끝까지 정렬되지 않는다면 플래그는 아무런 역할도 하지 못하고 시간만 까먹게 될 것이다. 하지만 거의 정렬된 레코드에 대해서는 이 플래그가 확실히 효과가 있는데 이미 정렬된 배열에 새로운 레코드가 삽입되었을 때는 루프 반복 회수를 대폭 줄일 수 있다. "abdfskz"를 이 방법으로 정렬할 경우 s와 k만 바꾸면 정렬이 완료된다.