정렬 알고리즘

• 상위 문서: 수학 관련 정보, 컴퓨터 관련 정보
• 관련 문서: 점근 표기법, 정렬/예제

1 개요

전산학자에게 물어보면 며칠을 떠들게 시킬 수 있는 주제. 관심있는 전산학과 출신이 있다면 퀵소트에 대해 물어보자.

정렬을 설명할때 보여주기 좋은 영상이다
뽀오오오오오오옥
정렬 알고리즘을 소리로 표현한 영상이다. 15가지의 정렬이 나타나 있다.

컴퓨터 분야에서 중요시되는 문제 가운데 하나로 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제이다. 실제 컴퓨터 분야에서 사용하는 데이터의 경우 숫자의 순서나 어휘의 순서대로 정렬한 다음 사용해야 되는 경우가 거의 항상 발생하는데 이걸 얼마나 효과적으로 해결할 수 있느냐가 정렬 문제의 핵심이다.

데이터를 정렬해야 하는 이유는 탐색을 위해서이다. 사람은 수십에서 수백 개의 데이터를 다루는 데 그치지만 컴퓨터가 다뤄야 할 데이터는 보통이 백만 개 단위이며 데이터베이스 같은 경우 이론상 무한 개의 데이터를 다룰 수 있어야 한다. 탐색할 대상 데이터가 정렬되어 있지 않다면 순차 탐색 이외에 다른 알고리즘을 사용할 수 없지만 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다. 삽입과 삭제가 자주 되는 자료의 경우 정렬에 더 많은 시간이 들어가므로 순차 탐색을 하는 경우도 있지만 대부분의 경우 삽입/삭제보다는 데이터를 조회하는 것이 압도적으로 많고 조회에 필요한 것이 바로 검색이다.

이미 정렬된 데이터의 특징은 어떤 값을 임의로 집었을 때 해당 값을 집은 위치의 오른쪽에는 무조건 그것보다 크거나 같은 값이 있고, 그 위치의 왼쪽에는 무조건 그것보다 작거나 같은 값이 있다는 것이다. 따라서 컴퓨터가 어떤 값을 딱 집었을 때 찾고자 하는 값보다 집어올린 값이 작다면 그 위치보다 왼쪽은 볼 필요가 없다. 그보다 오른쪽만 보면 된다. 컴퓨터가 어떤 값을 집어올리는 위치가 후보군의 가운데인 탐색 알고리즘이 이진 탐색 알고리즘이다. 이진 탐색 알고리즘은 최악의 경우라도 [math]\log n[/math]의 성능을 보이는데 예를 들어 43억 개의 정렬된 자료가 들어있는 데이터에서 어떤 값을 찾아야 할 때 최악의 비교 횟수(찾는 값이 없는 경우)는 겨우 32회에 불과하다. 33회 비교시에는 약 86억 개의 자료를 탐색할 수 있다. 더 발전한 알고리즘인 비례탐색 알고리즘(찾는 값이 후보군의 최소값과 최대값 사이의 몇 % 위치에 있는지 계산)은 더 적은 횟수의 비교로 원하는 값을 찾아낼 수 있다. 컴퓨터에서 정렬을 수행하는 이유 중 가장 큰 이유가 바로 이 이진 탐색이 가능한 데이터를 만들기 위해서이다.

보통 컴퓨터 분야에서 연구되는 문제들의 경우 사람들이 푸는 방식을 흉내내는 경우가 많은데, 정렬 문제 역시 사람들이 푸는 방식을 흉내낸 형태이다. 주어진 데이터들이 있으면 값들을 서로 비교하여 순서에 맞게 자리를 바꿔주는 형태로 정렬을 하는데 이를 "비교정렬"이라고 부른다. 일반적으로 많이 쓰이는 정렬방법이고 만들기도 굉장히 쉬운 편이다. 그 외에 비교를 하지 않고 데이터를 보는 순서대로 나열하는 방식이 있긴 한데 이는 조금 특수한 경우에만 사용할 수 있다. 아주 간단한 예로 우편함 방식을 들 수 있다. "이름을 봐야되니 비교를 하지 않나요?"라고 질문하는 경우가 있는데 아니다. 약간 조작하면 비교없이 바로바로 집어넣을 수 있다.

전문적인 이야기를 최대한 생략하고 설명하면 입력된 데이터의 크기를 n이라고 했을 때 비교정렬의 경우에는 [math]n^2[/math]번만큼 비교를 해야 정렬이 되는데 알고리즘 연구하는 사람들 입장에서 보면 이게 비효율적인 방식이다. 그래서 온갖 수단과 방법을 동원해서 현재는 대략 (nlgn)번 비교할 수 있도록 줄인 상태이고 비교정렬의 경우 여기서 더이상 줄일 수 없다고 증명되었다. 비교를 하지 않는 방법의 경우에는 데이터의 종류에 따라 다르지만, 그보다 더 작은 시간복잡도로도 정렬이 되는 것이 가능하다.

비전공자의 경우 "그게 뭐 그리 어려운 가요?"라고 생각하는 사람들이 많은데 아주 효과적인 정렬방법을 만들기 위해서는 온갖 잔머리와 테크닉, 지혜, 아이디어를 갈아넣어야 된다. 농담이 아니라 정렬 문제 하나만 파서 박사학위까지 따는 경우도 있다. 빌 게이츠의 경우, 팬케이크 정렬을 구현하는 알고리즘을 냈는데 대체할 알고리즘이 나오기 까지 30여년이 걸렸다고. 근래에는 많은 효과적인 정렬 방법들이 개발돼서 정말 획기적인 것을 제시하는 거 아니면 박사학위까지 가는 것은 좀 힘들긴 하겠지만…

이론과 달리 실제로 돌려보면 의외로 결과가 다르게 나오는 경우가 종종 있다. 주로 하드웨어 입출력이 관여해서 그 부분에 걸리는 시간이 정렬 알고리즘마다 과하게 달라서 더 느려야 하는 알고리즘이 더 빠르다던가, 아니면 정렬된 자료들을 대상으로 퀵소트 VS 다른 정렬 알고리즘에서 자주 관찰되는 현상인데, 이론상으로는 정렬된 알고리즘에서는 퀵소트가 더 느려야 하지만, 비교하는 기준점이 하나로 고정되어서 그 기준점이 많은 비교를 행하는 퀵소트 특성상 레지스터에 비교하는 기준점 원소를 올려놓고 신속하게 메모리에서 다음 비교할 원소를(그것도 메모리에서 연속된) 예측하여 가져오는 경우, 이 과정이 다른 정렬 알고리즘의 메모리에서 레지스터로 올리는 과정에 걸리는 시간이 생략되어 오히려 더 빠른 경우를 볼 수 있다. 이에 관해서는 컴파일러나 하드웨어 등등의 관점에서 자세히 다룬 논문들이 차고 넘치니 참조하도록 하자.

2 대표적인 정렬의 종류

실제 응용에서는 상황에 따라 두 가지 이상의 정렬 방법을 사용하는 경우가 많다. 예를 들면, 정렬 대상이 특정 크기 이하로 단편화될 때 까지는 퀵정렬을 쓰다가, 그 특정 크기 이하가 됐을 때에는 작은 규모에서 강점을 보이는 삽입정렬을 쓴다거나. 혹은 특정 횟수 이상 재귀호출이 발생하면 O(n lg n)이 보장되는 힙정렬을 쓴다거나.

2.1 [math] O(n^2) [/math]인 것

대개 계산 시간이 정렬할 자료의 수의 제곱에 비례해서 늘어난다. 즉, 1만 개를 1초에 정렬하면 10만 개를 정렬하는 데에는 100초 정도가 필요하다.

2.1.1 버블 정렬(Bubble Sort)

이 문단은 거품 정렬 · 버블 정렬(으)로 검색해도 들어올 수 있습니다.

버블 정렬을 실행했을 때 나오는 그림.

1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ..., n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n-2번째와 n-1번째까지, ...해서 최대 [math]\displaystyle \frac{n(n-1)}{2}[/math]번 정렬한다. 한 번 돌 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여 거품정렬이다.

거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. 이미 정렬된 자료를 정렬하는 바보짓을 왜 하냐는 의문이 들 수 있지만, 정렬 알고리즘은 자료가 정렬되어 있는지 아닌지는 모르고 작동하기 때문에 의미가 있다.
가장 손쉽게 구현하여 사용할 수 있지만, 만들기가 쉽고 직관적일 뿐이지 알고리즘적 관점에서 보면 대단히 비효율적인 정렬 방식이다. 다른 몇 가지 정렬 방식과 비교해도 효율이 대략 시망.

이해하기 쉽고 코드가 짧은 덕에 각종 교습서에서 정렬 알고리즘의 예시로 많이 보여주며, 입력량이 작으면 어지간한 비효율적인 방법도 씹어먹고 수행이 가능하지만 실제 개발에서는 전혀 쓰이지 않는다고 봐도 무방하다. 정말 어지간한 경우가 아닌 이상 버블 소트는 피해야 한다. 요즘은 웬만한 프로그래밍 언어 내부에 온갖 꼼수를 다 갈아넣은 고효율의 정렬 알고리즘이 내장되어 있어, 그냥 인클루드해서 갖다 쓰기만 하면 되는 세상이라 버블 정렬의 장점이 거의 없다. 내장 정렬이 더 편하니 (...)

2.1.1.1 파생형

• 칵테일 정렬(cocktail sort)

셰이커 정렬(shaker sort)라고도 한다. 홀수 번째 돌 때는 앞부터, 짝수 번째는 뒤부터 훑는 정렬. 당연하겠지만 이 쪽은 마지막과 처음이 번갈아가며 정렬된다.

• 콤브 정렬(comb sort)

기본 형태는 버블정렬과 같지만 예를 들어 처음에 a[0]에서 10칸 띄워서 a[11]과 비교해서 치환하는 식으로 대상을 띄웠다가 한 바퀴 돌면 띄우는 간격을 좁혀서 정렬하는 방식이다. 이렇게 하면 버블정렬과 다를 게 없어졌을 시점엔 정렬이 거의 끝나 있는데, 이 단계까지 가는 동안 모양이 마치 닭의 볏을 닮았다 하여 콤브정렬이라는 이름이 붙었다. 이렇게 본다면 콤브정렬이 버블정렬보다 좋아 보이지만 단점이 있는데 버블정렬이 stable sort이지만 콤브정렬은 그렇지 못하다.

2.1.1.2 소스 코드

#include 

int* bubble_sort(int *array, int n); //버블 정렬 함수
int sort_result_print(int *array, int n); //정렬된 결과 출력 함수
int main(void) {
int arr[5] = {11, 3, 4, 6, 1}; //무작위로 선정된 5개의 수가 담긴 배열
printf("버블 정렬 알고리즘 예제\n");
printf("11, 3, 4, 6, 1의 5개의 수를 정렬\n");
printf("------------------------------\n");
bubble_sort(arr, 5);
sort_result_print(arr, 5);
return 0;
}
int* bubble_sort(int *array, int n) {
int i, j, temp;

for(i = 0; i 

2.1.2 선택 정렬(Selection sort)

이 문단은 선택 정렬(으)로 검색해도 들어올 수 있습니다.

선택 정렬을 실행했을 때 나오는 그림.

버블 정렬이 비교하고 바로 바꿔 넣는 걸 반복한다면 이쪽은 일단 1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훑어서 가장 작은 게 2번째……해서 (n-1)번 반복한다. 어찌 보면 인간이 사용하는 정렬 방식을 가장 많이 닮았다. 어떻게 정렬이 되어 있든 일관성 있게 [math]\displaystyle \frac{n(n-1)}{2}[/math]에 비례하는 시간이 걸린다는 게 특징. 또한, 버블 정렬보다 두 배 정도 빠르다

2.1.3 삽입 정렬(Insertion sort)

이 문단은 삽입 정렬(으)로 검색해도 들어올 수 있습니다.

삽입 정렬을 알기 쉽게 만든 그림.

k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식으로, 평균적으론 O(n²)중 빠른 편이나 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크며, 앞의 예시처럼 작은 게 뒤쪽에 몰려있으면(내림차순의 경우 큰 게 뒤쪽에 몰려있으면) 그야말로 헬게이트다.
다만 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다. 괜히 '삽입'이란 이름이 붙은 것이 아니다.

2.2 [math] O( n \log n ) [/math]인 것

이 세 알고리즘은 최선이나 평균적으로나 [math] O( n\log n ) [/math]의 성능을 나타낸다. 최악의 상황에서도 병합정렬이나 힙정렬은 [math] O( n \log n ) [/math]을 유지하는 반면 순수한 퀵정렬은 오히려 [math] O( n^2 ) [/math]으로 뒤진다. 하지만 실제로는 퀵소트를 조금 개량해서 최악의 경우가 발생하지 않도록 코드를 짠다. 이 알고리즘들은 서로만의 특유한 성질과 장단점이 있다.

2.2.1 병합 정렬(Merge sort)

병합 정렬의 예.

개발자는 존 폰 노이만으로 원소 개수가 1 또는 0이 될 때까지 두 부분으로 자른 뒤 자른 순서의 역순으로 크기를 비교해 병합해 나간다. 병합된 부분 안은 이미 정렬되어 있으므로 전부 비교하지 않아도 제자리를 찾을 수 있다. 대표적인 분할 정복 알고리즘으로 존 폰 노이만의 천재성을 엿볼 수 있는 알고리즘이다.

성능은 아래의 퀵정렬보다 전반적으로 뒤떨어지고, 데이터 크기만한 메모리가 더 필요하지만 최대의 장점은 데이터의 상태에 별 영향을 받지 않는다는 점과 stable sort라는 점이다. 힙이나 퀵의 경우에는 배열 A[25]=100, A[33]=100인 정수형 배열을 정렬한다고 할 때, 33번째에 있던 100이 25번째에 있던 100보다 앞으로 오는 경우가 생길 수 있다. 그에 반해서 병합정렬은 그런 거 없다.

2.2.2 힙 정렬(Heap sort)

단계별로 보는 힙정렬 알고리즘. 왜 이건 춤추는게 없지

우선 힙이 뭔지 모른다면 힙 트리 항목 참고.

1. 원소들을 전부 힙에 삽입한다
2. 힙의 루트에 있는 값은 남은 수들 중에서 최소값(혹은 최대값)을 가지므로 루트를 출력하고 힙에서 제거한다.
3. 힙이 빌 때까지 2의 과정을 반복한다.

사실 선택 정렬과 거의 같은 알고리즘으로. 단지 가장 큰 원소를 뒤로 보내는 데에 단순히 매번 쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점이다.

힙정렬은 추가적인 메모리를 전혀 필요로 하지 않는다는 점과, 최악의 경우에 O(n²)의 성능을 내는 퀵정렬과 달리 항상 O(nlgn) 정렬의 성능을 발휘하는 장점이 있다. 하지만 실제 코드를 짜서 비교를 해 보면 퀵정렬이 힙정렬보다 일반적인 경우에 빠르게 동작한다.

2.2.3 퀵 정렬(Quick sort)

퀵 정렬의 적절한 예시.

퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 나타낸다. 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이다. C, C++, PHP, 자바 등 거의 모든 언어에서 제공하는 정렬 함수에서 퀵 정렬 혹은 퀵 정렬의 변형 알고리즘을 사용한다. 방식은 적절한 원소 하나를 기준(피벗, pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은 것, 큰 것으로 나눈뒤 나누어진 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다.

위에서도 말했듯이 최악의 경우에는 시간복잡도가 O(n²)가 되는데, 피벗을 최솟값이나 최댓값으로 계속해서 잡게 되는 경우에 그렇다. 대표적인 예로는 피벗을 항상 배열의 첫 원소로 잡도록 구현한 알고리즘으로 이미 정렬된 배열을 정렬할 경우. 힙정렬이나 병합정렬은 이런 경우가 없지만, 데이터가 극단적이면 대충 구현된 퀵정렬은 안쓰느니만 못한 최악의 결과를 초래한다. 이를 방지하기 위하여 여러 기법들이 개발 되었는데, 대표적인 것이 피벗을 랜덤으로 잡는 것. 또는, 배열 중에 3개나 9개의 원소를 골라서 이들의 중앙값을 피벗으로 고르는 것이다. 이 방법을 사용하더라도 최악의 경우가 나올 수는 있지만 그 경우가 극히 드물게 된다. 재귀 깊이가 어느 제한 이상으로 깊어질 경우 힙 정렬 알고리즘을 사용하여 항상 O(n log n)을 보장해주는 방법도 많이 쓰인다.

링크드 리스트 역시 퀵정렬이 가능하다. 첫번째 노드 A를 피벗으로 놓고 나머지 노드들 중 피벗보다 작은 것들은 L1, 큰 것들은 L2로 연결한다. L1과 L2를 퀵정렬한 뒤 L1->A->L2 순으로 연결하면 정렬 완료. 힙소트나 머지소트 역시 가능.

단, 파이썬은 퀵정렬을 하지 않는다. 그 이유는 파이썬은 stable한 정렬을 하는데, 퀵정렬은 stable하지 않기 때문이다. 예를 들어 한글의 키값이 2, 숫자의 키값이 1이라 두면 1, ㄱ , ㄷ, ㄹ, 2를 퀵정렬해서 2, 1, ㄹ, ㄱ, ㄷ 같은 게 나올 수도 있다. O(n)의 추가 메모리를 이용하면 stable한 퀵정렬을 만들 수 있다.

현존하는 컴퓨터 아키텍처 상에서 비교 연산자를 이용하여 구현된 정렬 알고리즘 중 가장 고성능인 알고리즘이 바로 이 퀵정렬이다. 단 데이터에 접근하는 시간이 오래 걸리는 외부 기억장소(하드디스크 등)에서 직접 정렬을 수행할 경우에는 병합 정렬이 더 빠른 것으로 알려져 있다. 요즘에는 디스크에서 데이터를 블럭 단위로 읽어서 각각을 퀵정렬한 뒤 정렬된 두 블럭을 병합정렬하는 식으로 알고리즘을 설계한다.

2.3 그 밖에

2.3.1 기수 정렬(Radix sort)

파일:Radix sort.gif
기수 정렬 알고리즘 중 LSD를 시각화한 것.

O(kn) (k는 데이터의 자릿수를 의미한다.)

위에 나온 알고리즘은 모두 데이터끼리의 직접적인 비교를 이용하는데, 이렇게 데이터끼리 직접적인 비교를 하여 정렬할 경우 시간복잡도는 O(nlogn)보다 작아질 수 없다. 이 기수 정렬은 자릿수가 있는 데이터(정수, 문자열 등)에서만 수행이 가능하며, 데이터끼리의 직접적인 비교 없이 정렬을 수행한다. 비교를 이용한 정렬이 아니기 때문에 k가 상수일 경우 시간복잡도가 O(n)으로 퀵정렬보다 빠른 시간복잡도가 나오는 것이 가능하다. 어떻게 데이터끼리 비교하지도 않고 정렬을 할 수 있는지는 후술. 다만 이 알고리즘은 자릿수가 적은 4바이트 정수 등에서나 제대로 된 성능을 발휘할 수 있으며, 자릿수가 무제한에 가까운 문자열 정렬 등에 사용할 경우 오히려 퀵정렬보다 느릴 수 있고, 부동 소수점 등을 정렬할 때는 아예 사용할 수가 없다.

기수 정렬의 방식은 대충 이렇다. 데이터가 n진법이라고 가정하자. 0번부터 n-1번까지의 리스트를 만들어 놓고, 각 데이터를 순서대로 현재 자릿수의 숫자가 가리키는 리스트에 밀어넣고, 리스트를 0번부터 n-1번까지 순서대로 이어붙인다. 이 과정을 가장 낮은 자릿수부터 가장 높은 자릿수까지 반복하면 정렬이 끝나게 된다.

(예시) 10, 5, 15, 234, 1: 10진법, 최대 3자리 수인 정수들을 정렬해보자. 편의상 010, 005, 015, 234, 001로 표기.

10⁰의 자리: 0) 010, 1) 001, 4) 234, 5) 005, 015. 순서대로 이어붙이면 010, 001, 234, 005, 015.
10¹의 자리: 0) 001, 005, 1) 010, 015, 3) 234. 순서대로 이어붙이면 001, 005, 010, 015, 234.
10²의 자리: 0) 001, 005, 010, 015, 2) 234. 순서대로 이어붙이면 001, 005, 010, 015, 234.

보다시피 마지막 자리까지 과정을 거치면 정렬된 결과인 1, 5, 10, 15, 234가 나온다. 실제 프로그램에서 정수를 정렬하는 코드를 짜는 경우, 10진법 대신 컴퓨터가 바이트 단위로 처리하기 쉬운 2진법을 사용하고, 각 자릿수를 정렬하는 과정은 밑의 카운팅 정렬을 이용하는 경우가 많다. 그렇게 코드를 짜면 퀵 정렬보다도 훨씬 빠른 속도로 정수를 정렬할 수 있다. 다만 위에 설명된 대로 이는 자릿수가 적은 상황에서만 그렇고 대부분의 경우에는 그렇지 않다.

그 이유는 시간 복잡도가 엄밀하게는 O(n)이 아니라 O(n * 자릿수)이기 때문이다. 해당 데이터의 자릿수는 상수로 간주하지만 어쨌든 log(표현 가능한 값의 수)에 해당되므로, 데이터의 숫자가 표현 가능한 값의 전체 숫자보다 더 큰 경우(물론 여러 값들이 중복해서 나타날 것이다)가 아니면 자릿수 자체가 logn 보다 크기 때문이다.

2.3.2 카운팅 정렬(Counting sort)

O(n+k) (k는 데이터의 최댓값을 의미한다.)

카운팅 정렬은 가장 큰 데이터에 따라 효율이 좌지우지된다. 쉽게 설명하자면 특정 데이터의 개수(1이 두 개 있다면 2)를 데이터의 값에 대응하는 위치에 저장한 뒤, 자신의 위치에서 앞에 있던 값을 모두 더한 배열을 만든 뒤, 거기서 데이터가 들어가야 할 위치를 찾아내는 정렬 알고리즘이다. 이 경우에 데이터의 최댓값을 k라 두면, 시간 복잡도는 O(n+k). 하지만, 만약 k가 억 단위를 넘어간다면? n이 아무리 작아도 동작시간이 크다. 그럴 땐 위의 정렬들을 사용하는 게 바람직하다. 반대로 k가 매우 작다면, 오히려 선형시간의 효과를 볼 수 있다. 즉, k가 작다는 조건이라면 매우 효율적인 정렬. 또한 카운팅 정렬은 배열을 사용하는 특성상, 정수라는 전제를 깔고 한다.

2.3.2.1 실행 과정

1. 자료를 탐색해서 그 최댓값을 구한다.
   • input = [1, 5, 4, 6, 3, 7, 8, 9, 10, 2]
   • 최댓값: k = 10
2. k+1만큼의 크기로 모든 자료가 0으로 초기화된 배열을 생성한다.
   • 배열 counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (11개)
3. input의 모든 원소 n에 대하여 counts의 n에 대응하는 곳에 +1을 해준다.
   • counts = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
   • 이때 counts[n]은 배열 input에 n이 몇 개 있는지를 의미한다.
4. counts[i] += counts[i-1]의 점화식을 1부터 k의 위치까지 행한다.
   • counts = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
   • 이때 counts[n]은 배열 input에 n 이하의 원소가 몇 개 있는지를 의미한다.
5. 길이가 counts[k]인 배열을 하나 더 생성한다.
   • 배열 ans = [N, N, N, N, N, N, N, N, N, N] (10개, N은 Null)
6. counts의 input[0]에 대응하는 곳의 원소를 찾아서 t로 놓는다. 이제 ans의 t-1에 대응하는 곳에 input[0]을 저장하고, counts의 input[0]에 대응하는 곳의 값은 -1 해준다.
   • 1이 주어짐
   • counts[1] = 1
   • 대응하는 값인 1-1=0의 위치에 1을 삽입
   • ans = [1, N, N, N, N, N, N, N, N, N]
   • counts는 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]에서 [0, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10]로 바뀜
7. 6의 과정을 남아 있는 자료에 대하여 반복한다.
   • 5가 주어짐
   • counts[5] = 5
   • 대응하는 값인 5-1=4의 위치에 5를 삽입
   • ans = [1, N, N, N, 5, N, N, N, N, N]
   • counts는 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]에서 [0, 0, 2, 3, 4, 4, 6, 7, 8, 9, 10]로 바뀜
   • ...
8. 이런 식으로 n개의 자료를 모두 조사하면 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]순서로 정렬이 된다.

2.3.3 셸 정렬(Shell's sort)

삽입 정렬이 거의 정렬된 배열에서 최적의 성능을 내는 것에서 착안한 정렬 방법이다. 삽입 정렬을 띄엄띄엄한 간격으로 먼저 수행하고, 그 간격을 점차 좁혀나가면서 최종적으로는 거의 정렬된 배열을 삽입 정렬로 마무리하게 된다. 지저분해 보이지만 삽입 정렬의 특성을 잘 이용한 정렬로, 실제 성능은 힙 정렬 등에 버금갈 정도로 빠르다! 이 정렬 알고리즘의 핵심은 어떤 간격으로 정렬을 수행해 나갈 것이냐는 것인데, 그 간격에 따라 시간 복잡도도 제각각이다. 그 간격을 잘 선택하는 경우 O(n^1.25)까지도 가능하다고 하는데 일반적인 데이터 크기에 모두 적용할 수 있는 것은 아니다. 알고리즘 자체가 시간 복잡도가 명확하지 않고 퀵 정렬이나 병합 정렬에 비해 크게 나을 것이 없기에 일반적으로 쓰는 알고리즘은 아니다. 셸 정렬이란 이름은 개발자인 도널드 셸의 이름을 딴 것으로 유닉스의 셸과는 관련이 없다. 이것을 잘 몰랐는지 예전 번역서에는 '껍질 정렬'로 오역된 책이 있었다. 지금도 껍질 혹은 틀을 의미한다면서 큰 틀을 잡아나가면서 정렬해나가기에 셸 정렬이라는 말이 가끔 도는데 완전히 틀린 말이다.

2.3.4 보고 정렬(Bogo sort, stupid sort)

O(∞) (...)
언젠가는 저 많은 자료가 정렬될 것을 알기에, 당신의 의지가 충만해진다.

이름 그대로 멍청한 정렬이다. 랜덤으로 데이터들을 재배열한 후, 정렬되었는지 검사한다. 정렬이 되어있지 않으면 다시 랜덤으로 재배열한다. 정렬될 때까지 재배열한다. 덕분에 최악의 경우 정렬이 영원히 안 끝날 수도 있다! 물론 정렬된 데이터는 재배열 없이 한 방에 끝난다.

하지만 이 보고 정렬은 유전 알고리즘과 결합하면 나름 쓸만해지게 된다. 데이터에 따라서는 하나의 값만으로 크기를 비교할 수 없는 경우도 있다. 예를 들어 n차 다항식을 풀어서 나오는 결과값으로 정렬해야 하는 경우도 있는데 이런 데이터는 위에 나온 모든 정렬 알고리즘들이 다 소용없어진다. 이때 n차 다항식은 배열에서 데이터의 현재 위치까지 변수에 들어있는 등 사전에 계산해두는 게 불가능한 데이터이다. 이때 적절한 평가 함수와 유전 알고리즘을 조합하고 나서 유전 알고리즘의 후손 생성 알고리즘에 이 보고 정렬을 결합하는 것이다. 정말로 멍청하게 정렬된 후손은 도태되고 조금이라도 우수하게 정렬된 후손이 선택되는 과정이 반복돼서 최종적으로는 완전히 정렬된 데이터가 나온다.

다만 유전 알고리즘의 단점을 그대로 물려받는데, 정답이 언제 나올지는 아무도 모른다. 다만 실제로 돌려보면 대자연의 신비인지 생각보다 빠른 시간 안에 정답으로 수렴해간다.

2.3.5 보고보고 정렬(Bogobogo sort)

보고 정렬의 상위호환
관련 자료
보고 정렬을 이용해 만든 더욱 비효율적인 정렬 알고리즘이다.(...)

보고 정렬은 위 문단에서 기술했듯이 "랜덤으로 데이터들을 재배열한 후, 정렬되었는지 검사" 하는 알고리즘이다. 보고보고 정렬은 보고 정렬의 "정렬되었는지 검사"하는 과정에서 처음부터 끝까지 순차적으로 검사하는게 아니라 보고보고 정렬을 재귀 호출하는 다른 알고리즘을 쓴다. 그 검사 알고리즘은 아래와 같다.

1. 검사되어야 할 데이터의 카피를 만든다.
2. 그중 첫 n-1개의 데이터를 보고보고 정렬한다.
3. n번째 숫자가 첫 n개의 데이터 중에서 가장 큰지 확인한다. 그렇다면 이 데이터는 정렬되었다. 아니라면 랜덤으로 데이터를 섞은 뒤 2로 돌아간다.
4. 이 리스트가 원래의 리스트와 순서가 같은지 검사한다. 맞다면 이 리스트는 정렬된 것이다.

이 검사를 통과하지 못한다면 데이터를 섞은 뒤 다시 이 방법으로 정렬 여부를 확인한다.
참고로 2의 재귀호출 덕분에 이 짓거리를 n=2 에서부터 시작해야 한다. 거기다 스텝 3에서는 (n-1)/n의 확률로 스텝 2에서 겨우겨우 정렬됬던 n-1개 데이터를 다시 섞어버린다.그러면 다시 n-1개 데이터을 보고보고 정렬해야 한다......아 씨바 할 말을 잃었습니다

2.3.6 취침 정렬(Sleep sort)

이건 어디까지나 웃자고 만든 것일 뿐이다.

#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

int main(int argc, char **argv) {
while(--c > 1 && !fork());
slееp(c = atoi(v[c]));
printf("%d\n", c);
wait(0);
return 0;
}

실행 결과:

$ ./a.out 5 1 3 2 11 6 4
1
2
3
4
5
6
11

간단히 설명을 하자면, 프로세스를 정렬할 배열 숫자만큼 생성한 뒤, 각 프로세스마다 각자 숫자를 하나씩 주면서 그 숫자의 시간만큼 슬립시킨다.
먼저 일어나는 프로세스부터 각자 가진 숫자를 표시한다(...).

시간 복잡도는 대충 O(n+k)(k는 데이터의 최댓값) 정도 되는데, 프로세스 n개를 생성하는 시간과 그 프로세스들이 슬립하는 시간에 비례할 것이기 때문이다. n이 적당히 작은 경우 O(k)이라고 봐도 좋겠다.
수학적 해석을 위해서 사실과는 다르지만 컴퓨터가 프로세스를 하나씩 돌린다고 가정하면 O(nk)이라고 할 수 있겠다.

근데 이 알고리즘은 레이스 컨디션이라는 문제를 간과하고 있다. 모든 fork된 프로세스가 순진하게 round robin으로 돌 거라 생각하면 안 된다. 저게 숫자가 작을 때는 문제가 안 되는데 만약 억 단위의 숫자를 정렬한다거나(시간도 억 단위로 걸리겠지만) 슬립 타이머를 마이크로초 이하로 아주 짧게 잡는다면 정렬이 완전하게 되지 않고 대략적으로 정렬이 된다. 즉 정렬 결과에 '노이즈'가 낀다.

사실 알고리즘의 정의상 슬립 정렬은 실행 환경에 따라 결과가 달라지므로 '알고리즘'이라 부를 수 없다. 단지 '메서드'일 뿐이다.

2.4 참고 문서

• 정렬/예제
• 프로그래밍 언어
• 자료구조
• 알고리즘#s-6