정렬(Sort)
정렬(sorting)이란 크기가 제 각각으로 나열된 데이터를 크기의 순서대로 다시 나열하는 작업을 뜻한다. 정렬되지 않은 데이터를 크기가 커지는 순서로 나열하였으며 이를 데이터를 오름차순으로 정렬한다고 한다. 이와는 반대로 크기가 작아지는 순서로 데이터를 나열한 경우를 내림차순으로 정렬한다고 한다.
정렬은 컴퓨터 알고리즘 중에서 가장 기초적이고 기본적인 알고리즘으로서 화일처리, 데이터베이스, 인터넷 등의 다양한 응용 분야에서 데이터를 탐색 또는 검색하고자 할 경우 반드시 필요로 하는 작업이다. 사용하고자 할 데이터를 한번 정렬시켜놓으면 이후의 탐색 과정이 매우 간단해지고 빨라지기 때문에 탐색에 앞서 데이터를 정렬시키는 것이 일반적이다. 정렬 알고리즘을 평가하는 기준은 데이터간의 비교 횟수, 데이터의 이동 횟수, 사용되는 메모리의 양 등이다. 내부 정렬은 데이터가 메모리에 있는 경우를 가정하므로 공간적 복잡도(space complexity)는 실질적으로 중요하지 않으며, 데이터의 비교 횟수와 이동 횟수는 시간적 복잡도(time complexity)에 직접 영향을 주는 중요한 사항이다. 지금부터 논의할 기초적인 방법들은 개의 데이터를 정렬하기 위하여의 시간적 복잡도를 가진다. 보다 지능적인 방법들은 대체로의 시간적 복잡도를 가지게 되어 보다 효율적이라 할 수 있다.
삽입정렬은 정렬되어 있는 레코드에다 새로운 레코드를 적절한 위치에 삽입하는 방법을 사용한다. 리스트를 가상적으로 왼쪽과 오른쪽 리스트로 구분하자. 왼쪽 리스트의 레코드들은 이미 정렬이 되어 있고, 오른쪽 리스트에는 정렬을 해야할 레코드가 들어있다. 오른쪽 리스트의 첫 번째 레코드가 왼쪽의 정렬된 리스트의 어느 위치에 삽입되어야 하는가를 판단한 후 제 위치에 삽입하는 것이다. 이 경우 삽입될 위치로부터 오른쪽에 있는 레코드들은 한 칸씩 오른쪽으로 이동시켜서 삽입될 위치를 비워두어야만 삽입이 가능해진다.
삽입 정렬은 알고리즘의 고유한 특성에 의해 필연적으로 많은 레코드들의 이동을 포함한다. 즉 배열로 이루어진 리스트들의 중간에 새로운 레코드를 삽입하려면 삽입된 위치의 오른쪽에 있는 레코드들은 한 칸씩 오른쪽으로 밀려야 한다. 그러므로 레코드의 크기가 크다면(예를 들어 1,000 Bytes) 얼마나 많은 시간을 데이터의 이동에 소모해야 하는지 상상해 보아라. 결과적으로 삽입 정렬은 데이터의 양이 많고 레코드가 클 경우에 적합하지 않음을 알 수 있다. 삽입 정렬의 가장 큰 장점은 필요한 경우에만 배열을 정렬한다는 점이다. 만일 배열이 정렬되어 있으면 레코드들을 전혀 이동할 필요가 없다. 따라서 삽입 정렬은 대부분의 데이터가 이미 정렬되어 있는 경우에 많이 사용된다. 또한 삽입 정렬은 데이터의 수가 매우 적을 경우 알고리즘 자체가 매우 간단하므로 보다 유리할 수 있다.
선택 정렬(Selection Sort)은 가장 작은 값을 선택하고 나열하는 과정을 반복하는 간단한 정렬 알고리즘 중의 하나이다. 먼저 입력 리스트는 배열에 저장되어 있고 배열에 존재하는 레코드 중에서 가장 키 값이 작은 레코드를 찾아서 첫 번째 위치에 있는 레코드와 교환한다. 다음에 다시 첫 번째를 제외한 나머지 레코드 중에서 가장 작은 값을 찾아 두 번째 위치의 레코드와 바꾸는 것이다. 이런 식으로 전체 배열이 정렬될 때까지 계속한다. 이 방법에서는 나머지 레코드 중에서 가장 작은 것을 선택하기 때문에 선택(selection)이라는 이름이 붙었다.
선택정렬은 가장 간단한 방법 중 하나이고 크기가 적은 리스트에는 매우 효과적인 방법일 뿐만 아니라 안정성을 만족하는 정렬 방법이다.
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 것이다. 버블 정렬이 이러한 비교-교환 과정을 정렬이 안된 리스트의 왼쪽에서 시작하여 오른쪽 끝까지 진행하게 되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 밀려나오게 된다. 이런 모습이 물 속에서 거품이 떠오르는 것과 유사하다고 해서 버블정렬이라는 이름이 붙게되었다. 정렬이 안된 왼쪽 리스트를 한번 스캔하면 리스트의 오른쪽 끝에 가장 큰 값이 위치하게 되고, 오른쪽 리스트는 방금 추가된 값을 포함하여 정렬된 상태가 된다. 이러한 스캔을 정렬이 안된 왼쪽 리스트에서 데이터의 개수만큼 반복하면 정렬이 완료된다. 만약에 이러한 스캔 과정에 있어서 한번이라도 교환이 발생하지 않으면 정렬이 완료된 것이므로 알고리즘은 중지한다.
셀 정렬은 Donald L. Shell이라는 사람이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 리스트에 대해서는 대단히 빠른 것에 착안한 방법이다. 이 방법은 감소 간격 정렬(diminishing increment sort)이라고도 한다. 셀 정렬은 삽입 정렬과는 다르게 전체의 리스트를 한번에 정렬하지 않는다. 셀 정렬은 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트(partition)를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트들이 정렬되면 셀 정렬은 다시 전체 리스트를 더 적은 수의 부분 리스트로 만든 후에 이러한 과정을 부분 리스트의 수가 1이 될 때까지 되풀이한다. 부분 리스트를 구성할 때는 주어진 리스트의 k번째 간격(gap)을 가지는 레코드들을 모아서 만든다. 셀 정렬에서는 각 스텝이 끝나면 간격 k를 줄여가므로 정렬 과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 수는 증가하게 될 뿐만 아니라 부분 리스트 내의 키 값들은 서로 어느 정도 정렬되는 경향을 가지게된다. 키들이 정렬되는 정도는 가속화되어 간격(k)의 값이 1이 되는 마지막 스텝에서는 상당히 정렬이 진행된 상태가 되며, 마지막으로 수행되는 삽입 정렬은 매우 신속하게 완료될 수 있다. 입력 데이터가 (41, 67, 14, 20, 49, 44, 38, 78, 7, 64, 25, 35, 3, 27, 52, 11)와 같을 때 셀 정렬이 수행되는 과정
삽입 정렬에 비하여 셀 정렬은 다음의 2가지 장점이 있다.(1) 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입 정렬에서는 한번에 한 칸씩만 이동된다. 따라서 교환되는 키들이 삽입 정렬보다는 최종적으로 정렬될 위치에 더 빨리 더 가까이 있을 가능성이 높아진다. (2) 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 수가 1이 되게 되면 셀 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 매우 빠르게 수행된다. 이것은 삽입 정렬이 거의 정렬된 리스트에 대해서는 매우 빠르게 수행되기 때문이다. 퀵 정렬은 정렬 알고리즘 중에서도 평균 실행 속도가 가장 우수하므로 다른 정렬 방법들보다 많이 사용되고 있다. 1960년에 C.A.R. Hoare에 의해 제안된 퀵 정렬 방법은 구현 과정이 그리 복잡하지 않으면서도 추가 메모리를 사용하지 않는 등 많은 장점을 가진 그야말로 빠른(quick) 정렬 방법이기 때문에 현재 퀵 정렬(Quick Sort)이라는 명칭으로 불리어지고 있다.
퀵 정렬 알고리즘은 주어진 전체 리스트를 정렬하기 위해서 전체 리스트를 2개의 부분 리스트로 나누고 각각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할-정복법을 사용한다. 이때 퀵 정렬에서 주어진 리스트를 두개의 분할된 리스트로 나누는 전략이 다소 특이하다. 먼저 주어진 리스트의 왼쪽 끝에 있는 데이터 값을 기준 값으로 설정한다. 이러한 기준 값을 피벗(pivot)이라고 부른다. 리스트 내의 모든 데이터는 설정된 피벗보다 작은 데이터는 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 데이터는 모두 피벗의 오른쪽으로 옮긴다. 결과적으로 피벗을 중심으로 왼쪽에 존재하는 모든 데이터는 피벗보다 작은 값들이고 오른쪽에 존재하는 모든 데이터는 피벗보다 큰 값들로 구성된다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 정렬하게 되면 전체 리스트가 정렬될 것이다. 사실 두개의 부분 리스트를 삽입 정렬로 정렬한다 해도 분명히 전체 리스트는 정렬될 것이고 피벗은 정확하게 정렬된 리스트에서 제 위치에 이미 존재하고 있을 것이다. 그러나 퀵 정렬은 이 상태에서 다시 왼쪽 리스트에서 새로운 피벗을 설정하여 왼쪽 리스트를 다시 두개의 부분 리스트로 분할하는 과정을 반복하게 된다. 당연히 오른쪽 리스트에 대해서도 동일하게 퀵 정렬이 적용된다. 이러한 과정은 부분 리스트들이 더 이상 분할될 수 없는 작은 크기(하나의 데이터만 리스트에 존재할 경우)를 가질 때까지 반복된다.
리스트의 첫 번째 값을 피벗(67)으로 설정하고 리스트의 왼쪽에서부터 오른쪽으로 조사해가다가 피벗보다 더 큰 값(90)을 찾으면 멈춘다. 다음에는 리스트의 오른쪽 끝에서부터 왼쪽으로 조사해가다가 피벗보다 더 작은 값(54)을 찾으면 멈춘다. 조사가 멈추어진 곳에 존재하는 두 값을 서로 교환한다. 이러한 조사와 교환 과정은 왼쪽과 오른쪽 조사 인덱스가 엇갈려 지나지 않는 한 계속 반복한다. 언젠가는 왼쪽 조사 인덱스와 오른쪽 조사 인덱스가 엇갈려서 지나가게 될 것이고 이 때 오른쪽 조사 인덱스가 가리키는 값(32)과 피벗(67)을 교환하게 되면 분할 과정이 종료된다.
합병 정렬은 두 개의 이미 정렬된 리스트를 합쳐서 하나의 정렬된 리스트로 합병하는 방법을 사용하여 정렬하는 방법이다. 즉, 하나의 리스트를 2개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다.
두개의 정렬된 부분 리스트를 합병하는 방법에 대하여 생각해보자. 여기에는 배열 list[]에 이미 정렬된 부분 리스트가 2개 있다. 왼쪽 부분 리스트는 list[low]부터 list[mid]까지 이고, 오른쪽 리스트는 list[mid+1]부터 list[high]까지 이다. 합병된 리스트가 저장될 배열 sorted[]가 있으며, 배열의 인덱스 3개가 사용된다. 인덱스 i는 왼쪽 부분 리스트에서 가장 작은 데이터를 가리키고(초기값 i=low), 인덱스 j는 오른쪽 부분 리스트에서 가장 작은 데이터를 가리키고 있다(초기값 j=mid+1). 인덱스 k는 합병될 리스트에서 다음 들어올 데이터의 위치를 가리킨다(초기값 k=low). list[i]와 list[j]를 비교해서 작은 값을 sorted[k]로 복사하고, 작은 값을 가리켰던 인덱스와 인덱스 k를 하나 증가시킨다. 이러한 과정을 하나의 리스트가 소진될 때까지 반복하고, 데이터가 남아있는 리스트는 배열 sorted[]로 비교 없이 복사한다. 여기에서 배열 sorted[]는 working space의 역할만 하며, 실제 데이터는 언제나 배열 list[]에 존재해야 하므로, 최종 정렬된 배열 sorted[]의 내용을 배열 list[]로 모두 재복사한다.
주어진 리스트를 정렬하기 위해서는 먼저 정렬된 2개의 부분 리스트가 필요하다. 정렬된 부분 리스트를 어떻게 만들 것인가? 이는 앞에서 공부한 분할-정복법을 이용하자. 즉 문제를 해결할 수 있을 만큼 계속해서 분할한 다음 정복하는 것이다. 주어진 리스트를 동일한 크기의 2개의 부분 리스트로 나누다보면 더 이상 분할할 수 없는 경우 즉 하나의 데이터를 가지는 부분 리스트가 생긴다. 이러한 두개의 부분 리스트를 계속 합병해나가면 전체 리스트가 합병되어 정렬되는 것이다.
합병 정렬은 원래의 배열 외에 같은 크기의 working space용 배열을 필요로 하므로 메모리를 많이 요구한다. 게다가 이러한 2개의 배열간에 많은 데이터 이동을 수반한다. 만약 레코드의 크기가 크고 레코드의 수가 많다면 합병 정렬은 대부분의 시간을 2개의 배열간 데이터 이동에 소모하게 되어 매우 비효율적이다. 이러한 단점을 해결하는 가장 좋은 방법은 레코드를 연결 리스트로 구성한 후 합병 정렬하는 것이다. 이렇게 되면 합병에 따른 데이터의 이동을 연결 리스트의 링크만을 재구성하여 이룰 수 있게 되므로 큰 레코드의 정렬에 매우 효율적일 수 있다. 2개의 배열을 이용하여 합병하는 알고리즘을 연결 리스트의 합병으로 확장하기 위해서 다음과 같은 구조체를 사용한다.
typedef struct
{ int key;
int link;
}linked;
이 구조체에서 링크 필드는 포인터형이 아닌 정수형 데이터로 되어 있음을 주의해야 한다. 초기의 link값은 모두 -1을 가진다. 이는 각 레코드가 독립된 하나의 부분 리스트임을 의미한다. 합병이 이루어지면 이러한 레코드들은 차례로 정렬된 순서를 유지하도록 연결되게 된다. 여기에서 인덱스 k는 항상 앞으로 갱신될 링크를 가진 레코드를 가리킴에 주의하라. 또한 정렬이 완료되면 list[n].link에 전체 리스트의 제일 작은 레코드를 가리키는 인덱스가 들어있다.
레코드가 연결 리스트로 구성하여 합병 정렬할 경우, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다. 따라서 크기가 큰 레코드를 정렬할 경우, 연결 리스트를 이용하는 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 크게 효율적일 수 있다.
히프 정렬은 최소 히프(minimum heap)를 사용하여 가장 작은 원소를 차례대로 추출하여 정렬하는 방법을 사용한다. 최소 히프는 이진트리의 특수한 형태인 완전이진트리(complete binary tree)이고 부모 노드(parent node)의 값이 자식 노드(children node)의 값보다 항상 작은 트리이다. 따라서 루트 노드(root node)의 값은 트리 내의 나머지 노드의 값보다 가장 작은 값을 가지게 된다.
리스트 (67, 90, 57, 25, 84, 32, 73, 54)를 최소 히프로 구성하는 과정을 나타낸 것이다. 최소 히프의 구성은 트리의 가장 아래(4번 노드)의 트리로부터 시작하여 가장 작은 최소 히프를 만들고, 점진적으로 작은 최소 히프들을 합치면서 보다 커다란 최소 히프를 만들어간다. 마지막으로 루트 노드를 포함한 모든 최소 히프를 합쳐서 하나의 전체 최소 히프를 구성하게 된다. 여기서 주의할 점은 이러한 반복은 n/2로 인덱싱되는 부모 노드로부터 시작하여 1로 인덱싱되는 루트 노드까지 역순서로 이루어진다는 점이다. 즉 최소 히프가 아래로부터 루프까지 점진적으로 구축됨에 주의하라.
일단 주어진 리스트로부터 최소 히프가 구성되면 루트 노드는 전체 최소 히프(전체 리스트)에서 가장 작은 값을 가지게 된다. 루트 노드의 값과 가장 마지막 리프 노드(leaf node)의 값을 교환하게 되면 가장 작은 값이 리스트의 제일 뒤에 위치하게 된다. 제일 뒤에 위치한 값은 이제 더 이상 고려할 필요가 없으므로, 리스트의 크기를 하나 줄이고 이에 따라 트리의 크기도 하나 줄인다. 이렇게 줄어든 트리는 루트 노드의 값이 바뀌었으므로 더 이상 최소 히프가 아니다. 따라서 루트 노드를 포함하는 adjust()를 다시 실행하여 왼쪽 최소 부분 히프와 오른쪽 최소 부분 히프를 합친 전체 최소 히프를 재구성한다.
이상의 과정에서 보듯이 히프 정렬은 리스트로부터 최소 히프를 구성하는 과정과 최소 히프에서 최소 값을 반복 추출하는 과정으로 이루어진다. 히프 소트는 전체 리스트를 정렬할 필요가 없는 경우에 적합하다. 예를 들어 제일 작은 데이터 10개만 필요한 경우 다른 정렬 방법은 전체 리스트를 정렬해야 하지만 히프 정렬은 최소 히프에서 10번만 작은 값을 추출해내면 된다.
문제 자체가 고유하게 가지는 복잡도를 문제의 하한(Lower Bound)이라고 하며, 이는 특정 문제를 해결하기 위해서는 어떠한 연산이 최소한 어느 만큼 필요한가를 의미하는 것이다. 이러한 문제 자체의 복잡도는 알고리즘의 복잡도와 혼동해서는 안된다. 알고리즘의 복잡도는 특정 문제를 특정한 방법으로 해결할 때 필요한 연산량으로서, 동일한 정렬 문제에 대해서도 삽입 정렬과 퀵 정렬은 서로 상이한 알고리즘의 복잡도를 가지게 된다. 비교 연산에 의한 정렬 문제의 복잡도 하한을 구하기 위해 결정 트리(Decision Tree)를 이용하고자 한다. 예를 들어 3개의 변수 a, b, c에 서로 상이한 임의의 값이 할당되어 있다고 가정했을 때, 3개의 변수를 정렬하기 위한 최소한의 비교 연산을 수행해보자. 여기서 주의할 점은 이러한 비교 연산의 수행은 특정 정렬 알고리즘의 동작과는 전혀 무관하게 이루어진다는 점이다. 예를 들어 변수 a와 변수 b가 비교되었다면 우리는 a가 b보다 작던지 아니면 a가 b보다 크다는 둘 중의 하나의 정보 외에는 얻을 수 없다.
결정 트리에서 각 노드(node)는 두 개의 변수 사이에 수행된 비교 연산을 나타내고, 각 가지(branch)는 비교 결과를 나타낸다. 루트 노드(root node)에서 하나의 리프 노드(leaf node)까지의 경로는 처음부터 수행된 비교 연산과 연산 결과를 뜻하고, 리프 노드는 이러한 연산 결과에 의하여 얻어진 정보에 의해 밝혀진 변수의 대소 관계를 나열(정렬)한 결과이다. 3개의 변수가 나열될 수 있는 경우의 수는이 되고, 3개의 변수를 정렬하는 결정 트리는 정확히 6개의 리프 노드를 가지게 된다. 예를 들어 a, b, c의 변수에 각각 2, 5, 8의 값을 할당했다면, 가장 왼쪽 경로에 의한 a?b 와 b?c의 비교 연산에 a, b, c의 순서로 정렬할 수 있음을 뜻한다. 이는 3개의 데이터를 정렬하고자 하면 최소한 3번의 비교 연산이 필요함을 뜻하게 된다.
키 값의 수치적인 표현을 이용하여 정렬하는 방법을 기수 정렬(Radix Sort)이라고 하는데 이는 일상생활에서도 많이 사용하는 방법이다. 예를 들어 도서를 저자 이름순으로 정렬하는 경우, 저자 이름의 첫 번째 글자가 동일한 글자일 경우, 저자 이름의 두 번째 글자를 사용하여 정렬하게 된다. 두 번째 글자도 동일하면 3번째 글자를 사용하여 비교한다. 즉 키들이 몇 개의 숫자나 글자로 이루어져 있는 경우 똑같은 위치에 있는 글자나 숫자를 이용하여 정렬을 하는 것이다. 이 정렬 방법은 키 안에 존재하는 글자나 숫자의 개수만큼 과정을 되풀이해야 할 것이다. 키를 아래와 같이 알파벳으로 표현한 경우나 이진수로 표현한 경우 모두 적용 가능하다.
기수정렬은 키들이 어떤 진법에서 표시된 수임을 적극적으로 이용한다. 예를 들어 세 자리의 숫자로 구별되는 서류를 정렬해야만 하는 사무원을 생각해보자. 제일 일반적인 방법은 10개의 박스를 만들어 100이하의 수를 위한 박스, 100에서 199까지의 숫자를 위한 박스, 200에서 299까지의 박스 등으로 구별하여 정렬하는 방법일 것이다. 이것은 10진법을 이용한 기수정렬의 원리이다. 기수정렬에서는 어떤 진법으로 표시된 키의 각각의 숫자에 의해 정렬을 한다. 컴퓨터는 10진법보다는 2진법을 더 좋아할 것이다. 이점에서 C언어는 다른 언어(예를 들어 파스칼)보다는 장점이 있는데 다른 언어에서는 키 값의 이진 표현을 직접 사용하는 것이 어렵다. 기수정렬에서 가장 낮은 자릿수를 먼저 사용하여 정렬한 다음, 그 다음 낮은 자릿수를 이용하는 방법을 최소 중요 숫자(Least Significant Digit : LSD) 정렬이라고 하고, 반대로 가장 높은 자릿수를 먼저 사용하는 방법을 최대 중요 숫자(Most Significant Digit : MSD) 정렬이라 한다. 보통 LSD 정렬도 가능하고 MSD 정렬도 가능하다. LSD 정렬방법의 경우 중간 과정의 서브파일들을 다시 정렬할 필요가 없으므로 일반적으로 LSD 정렬을 사용한다. LSD 기수 정렬의 방법은 오른쪽에서 왼쪽으로 비트나 숫자들을 조사하는 것이다.
각각의 상자는 1차 배열로 구현할 수도 있으나 매번 많은 자리 이동을 수반하므로 여기에서는 데이터의 이동을 최소화할 수 있도록 bottom과 up이라는 포인터 배열을 사용하고자 한다. 또한 리스트의 레코드들도 배열에 저장되지 않고 연결 리스트로 구성된다.
기수 정렬은 비교 연산 없이 단순한 분배 및 취합의 반복 수행(포인터 변환)만을 요구하므로 매우 빠르게 실행될 수 있다. 또한 데이터의 수가 증가하더라도 자릿수는 불변이므로 소요되는 시간이 선형적으로 증가하기 때문에 대용량의 데이터 정렬에 적합하다. 또한 대부분 사용되는 키 값은 학번, 사번, 주민등록번호 등이므로 기수 정렬에 쉽게 적용될 수 있다. 그러나 기수 정렬은 키가 특정한 형태를 가질 때만 사용이 가능하다. 예를 들어 실수, 한글, 한자 등으로 이루어진 키 값을 기수 정렬하고자 할 경우 매우 많은 상자(bin)가 필요하게 되므로 적용되기 어렵다.