정렬

$N$개의 수를 오름차순으로 정렬하는 알고리즘에 대해 알아보자. 내림차순이나 커스텀 정렬은 비교하는 기준만 바꾸면 된다.

버블 정렬

버블 정렬은 인접한 두 수를 비교하며 정렬하는 알고리즘이다. 다음을 반복한다.

1. 첫 원소부터 시작하여 인접한 두 개의 원소를 비교한다.
2. 앞의 원소가 뒤의 원소보다 크다면 두 원소의 위치를 바꾼다.
3. 같은 방법으로 총 $N-1$번의 비교를 수행한다. 이렇게 하면 가장 큰 수를 맨 뒤로 보낼 수 있다.
4. 모든 수가 정렬될 때까지 1~3번을 반복한다.

위의 시행을 한 번 시행할 때마다 수를 하나씩 정렬할 수 있다. 구체적으로 $i$번째 시행에서 $i$번째로 큰 수가 정렬된다. 따라서 위의 시행을 최대 $N$번 반복하면 배열을 정렬할 수 있다.

 

이름이 버블 정렬인 이유는 정렬되는 과정이 마치 거품이 일어나는 모습과 비슷하기 때문....인데 나는 동의할 수 없다. 이게 무슨 거품이라고?

장점

구현이 매우 간단하다.

단점

느리다. 다른 $O(N^{2})$ 정렬 중에서도 제일 느리다. CPU에서 비교 연산보다 교환 연산이 더 오래 걸리기 때문이다.

시간복잡도

$O(N^{2})$. 단 최선의 경우(이미 정렬되어 있는 경우), 시행을 마칠 때 배열이 정렬되었는지 확인하면 시간복잡도를 $O(N)$으로 줄일 수 있다. 밑에서 살펴볼 다른 $N^{2}$ 알고리즘도 같은 방법으로 최적화할 수 있다.

선택 정렬

선택 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분에서 최솟값을 찾아 정렬된 부분의 맨 뒤에 이어 붙이는 정렬이다. 주어진 배열 외에 추가로 메모리를 요구하지 않는 in-place sorting 알고리즘 중 하나이다.

 

구체적으로 다음을 반복한다. 맨 처음에는 배열 전체가 정렬되지 않은 부분이다.

1. 아직 정렬되지 않은 부분 중에서 최솟값을 찾는다. 
2. 최솟값을 정렬된 부분의 맨 뒤에 이어붙인다. 실제로는 정렬되지 않은 부분의 맨 앞에 있는 원소와 교환하는 방법으로 구현한다.
3. 원소가 하나 정렬되었으므로 정렬된 부분의 길이가 1 늘어나고, 정렬되지 않은 부분의 길이가 1 줄어든다.
4. 정렬되지 않은 부분의 길이가 1이 될 때까지 1~3번을 반복한다.

정렬되지 않은 부분의 길이가 0이 될 때까지 수행하지 않아도 되는 이유는 길이가 1인 배열은 그 자체로 정렬된 배열이기 때문이다. 따라서 정렬되지 않은 부분이 1개 남을 때까지 반복하면 배열을 정렬할 수 있다.

 

최솟값을 선택해서 정렬하는 알고리즘이라고 생각하면 되겠다. 

장점

자료를 최대 $N$번만 교환하므로 버블 정렬보다 빠르게 정렬할 수 있다.

단점

같은 수가 여러 개 있는 경우, 그 값들의 상대적인 위치가 바뀔 수 있다. 즉 정렬이 stable하지 않다. 참고로 stable 정렬이란 같은 수(또는 요소)가 여러 개 있을 때, 정렬 후에 그 수들의 상대적인 위치가 바뀌지 않는 정렬이다.

시간복잡도

$O(N^{2})$. 같은 $N^{2}$ 정렬과 비교하면 버블 정렬보다 빠르고 삽입 정렬보다 느리다. 교환 연산이 상대적으로 적기 때문이다.

삽입 정렬

정렬되지 않은 부분에서 수를 하나 뽑은 뒤, 정렬된 부분에서 그 수가 들어가야 할 위치를 찾아 삽입하는 정렬이다. 손 안의 카드 패를 정렬하는 방법과 비슷하다.

 

배열 구조상 가운데에 원소를 삽입할 수는 없으므로, 정렬된 부분에서 수가 들어가야 할 위치 뒤에 있는 수를 전부 한 칸씩 뒤로 옮긴 후 수를 삽입한다.

 

구체적으로 다음을 반복한다.

1. 삽입 정렬은 정렬된 부분을 앞에서부터 하나씩 늘려 나가는데, 길이가 1인 배열은 이미 그 자체로 정렬된 배열이므로 배열의 두 번째 원소부터 정렬해도 된다.
2. 현재 정렬할 원소와 정렬된 부분의 모든 원소를 비교하여 자신이 들어갈 위치를 찾는다.
3. 정렬된 부분에서 해당 위치 뒤에 있는 모든 원소를 한 칸씩 뒤로 옮긴다.
4. 정렬할 원소를 삽입한다.
5. 정렬되지 않은 모든 원소에 대해 1~4번을 반복한다.

원소의 위치를 찾아 삽입하는 정렬이라고 기억하면 된다. $i$번째 시행에서 $i+1$번 원소를 정렬하므로 위의 시행을 최대 $N-1$번 반복해야 한다.

장점

Stable 정렬이다. 즉 같은 값끼리는 상대적인 위치가 바뀌지 않는다. 또, 원소가 적은 경우 또는 대부분의 원소가 이미 정렬되어 있는 경우 효율적이다. 오히려 밑에 있는 로그 시간 정렬보다도 효율적일 수 있다.

단점

이동 연산이 많다. 원소가 매우 많거나 원소 하나하나가 큰 경우(구조체?) 비효율적이다. 원소를 옮기는 비용이 커지기 때문이다.

시간복잡도

평균, 최악의 경우 $O(N^{2})$. 최선의 경우 $O(N)$. 이미 정렬되어 있는 경우 각 시행당 한 번만 비교하면 되기 때문이다.

퀵 정렬

Stable하지 않지만 매우, 매우 빠르다. 괜히 quick이라는 이름이 붙은 게 아니다.

 

퀵 정렬은 배열을 두 부분으로 나눠 정렬하는 알고리즘이다. 전문 용어로는 분할 정복이라고도 하며, 아래에서 설명할 병합 정렬 역시 분할 정복이다.

 

배열에서 원소를 하나 고른다. 이 원소를 pivot이라 부르자. 배열에서 pivot보다 작은 값은 pivot의 왼쪽으로, pivot보다 큰 값은 pivot의 오른쪽으로 옮긴다. 왼쪽과 오른쪽 부분을 정렬해야 하는 것은 아니고, 순서 상관없이 일단 옮기기만 하면 된다.

 

이제 pivot은 정렬되었다고 볼 수 있다. pivot의 왼쪽에는 pivot보다 작은 값만, 오른쪽에는 pivot보다 큰 값만 존재하기 때문이다. 따라서 왼쪽과 오른쪽 부분을 정렬하기만 하면 된다. 어떻게 정렬해야 할까?

 

위의 과정을 그대로 반복하면 된다. 분할 정복에 의해 pivot의 왼쪽과 오른쪽이 각각 정렬될 것이다. 이제 원소가 1개 이하로 남을 때까지 배열을 쪼개면서 정렬을 진행하면 된다. 한 번의 시행마다 최소한 하나의 원소가 정렬되므로, 재귀가 반드시 끝난다는 사실을 알 수 있다.

pivot?

pivot을 고르는 방법은 정해져 있지 않다. 보통 맨 앞에 있는 원소를 pivot으로 고르지만, 랜덤으로 골라도 되고, 가운데 있는 값을 골라도 된다. 

장점

빠르다. 다른 로그 시간 정렬과 비교해도 압도적으로 빠르다. 한 번의 시행마다 원소들이 대략적으로 정렬되는 특성 때문이다.

 

정렬 과정에서 별도의 메모리 공간을 필요로 하지도 않는다. 단지 재귀 호출에 필요한 메모리만 필요할 뿐이다.

단점

오히려 배열이 이미 정렬되어 있는 경우 매우 비효율적이다. 이 경우의 시간복잡도는 무려 $O(N^{2})$. 피봇을 복잡하게 고르면 시간을 줄일 수 있다.

시간복잡도

평균적으로 한 번의 시행마다 비교 연산을 $N$번 수행하고, 배열이 절반씩 나눠지므로 시행 횟수는 평균적으로 $\log N$번이다. 따라서 퀵 정렬의 시간 복잡도는 $O(N\log N)$이다. 

 

하지만, 리스트가 계속 $1$개와 $N-2$개로 쪼개지는 최악의 경우 시간 복잡도는 $O(N^{2})$이다. 시행 횟수가 $N$번이기 때문이다.

병합 정렬

병합 정렬은 stable한 분할 정복 정렬이다. 배열을 최대한 크기가 비슷하게 좌우로 잘라 왼쪽과 오른쪽을 정렬한 후, 왼쪽과 오른쪽 배열을 합쳐 정렬한다. 좌우 배열 역시 병합 정렬로 정렬된다.

 

왼쪽과 오른쪽 배열을 합치려면 각 배열을 앞에서부터 탐색하면서 더 작은 수를 가져오면 된다. 

증명?

왼쪽과 오른쪽 배열을 정렬하는 방법 역시 병합 정렬이므로, 왼쪽과 오른쪽이 정렬된다고 가정했을 때 전체 배열도 정렬된다는 사실을 보이면 된다.

 

배열을 합칠 때, 왼쪽과 오른쪽 배열을 앞에서부터 보면서 더 작은 수를 먼저 가져온다. 따라서 합쳐진 배열도 오름차순으로 정렬될 것이다. 왼쪽과 오른쪽 부분이 정렬됐다고 가정하면 전체 배열도 정렬되므로, 귀납법에 의해 병합 정렬은 배열을 정렬할 수 있다.

장점

Stable하다. 

 

쪼개지는 두 배열의 크기가 거의 비슷하므로, 입력 데이터에 상관없이 정렬 시간이 일정하다. 퀵 정렬처럼 매우 느려지는 상황이 없다는 것이다. 이런 측면에서 보면 말 그대로 안정적인 정렬 방법이다.

단점

배열을 병합할 때, 수를 임시로 담을 배열이 필요하다. 그런데 각 요소의 크기도 매우 크다면? 큰 값을 많이 옮겨야 하므로 시간이 오래 걸릴 수 있다.

 

이런 경우에는 배열 대신 링크드 리스트를 사용하면 매우 효율적으로 정렬할 수 있다. 값을 복사하는 대신 링크만 바꿔주면 되기 때문이다.

시간복잡도

매 시행마다 배열을 이등분하므로 최대 $\log N$번 시행하며, 각 시행마다 배열을 합치는 데 평균 $N$번 비교 및 복사하므로 병합 정렬의 시간 복잡도는 $O(N \log N)$이다.

힙 정렬

힙 정렬은 단순히 힙에 원소를 전부 집어넣은 뒤 빼내는 알고리즘이다. 따라서 힙 정렬을 이해하기 위해서는 먼저 힙에 대해 공부할 필요가 있다.

힙

힙은 완전 이진 트리 형태로 원소를 저장하는 자료구조이다. 특이하게도 자료를 정렬하여 저장하기 때문에, 단순히 힙에 넣었다가 빼기만 하면 수를 정렬할 수 있는 것이다.

 

힙이 무엇인지는 자료구조 포스팅에서 설명하겠다.

 

최대 힙. 출처: 위키피디아

맨 위에 가장 큰 값이 있으면 최대 힙, 가장 작은 값이 있으면 최소 힙이다. 물론 커스텀 비교 식을 구현해도 된다.

 

값을 트리 형태로 저장한다고는 했지만, 트리를 구현할 때 배열을 주로 사용하는 만큼 실제로는 배열에 값을 저장하게 된다. $i$번 노드의 왼쪽 자식을 $2*i$번, 오른쪽 자식을 $2*i+1$번으로 놓고 구현하면 된다. (따라서 $i$번의 부모 노드는 $i/2$번이 될 것이다)

장점

삽입과 삭제 모두 로그 시간에 해결할 수 있는 힙 특성상 속도가 꽤 빠르고, 정렬된 처음 몇 개의 원소만 필요할 때 사용하면 좋다. 

단점

딱히..? 힙을 구현해야 한다는 점?

시간복잡도

힙에서 push와 pop 연산은 로그 시간에 수행된다. 따라서 $N$개의 원소를 push한 후 pop하는 힙 정렬의 시간 복잡도는 O$(N \log N)$이다.

기수 정렬 (Radix Sort)

기수 정렬은 수의 각 자릿값을 이용하여 정렬하는 알고리즘이다. 놀랍게도 천공 카드를 사용하던 20세기 시절부터 사용되던 알고리즘이다. 현재는 주로 이진 문자열과 정수를 정렬할 때 사용된다.

 

구체적으로는 자릿수가 같은 수를 같은 버킷에 담고, 버킷 순서대로 수를 늘어놓는 과정을 반복하게 된다. 

 

자릿수를 볼 때, 가장 낮은 자릿수부터 보는 LSD(Least Significant Digit) 방식과 가장 높은 자릿수부터 보는 MSD(Most...) 방식이 있다. MSD 방식은 문자열이나 모든 수의 길이가 같은 경우에 적합하다. 가장 큰 자릿수부터 보기 때문에 1부터 10까지의 자연수는 ``1, 10, 2, 3, ...``로 정렬된다. 참고로 MSD 정렬은 구현 방법에 따라 stable하지 않을 수도 있다.

 

수의 자릿수가 같다는 보장이 없다면, LSD 방식이 적합하다. MSD 정렬은 모든 값의 자릿수를 가장 큰 수의 자릿수에 맞춰 늘려야 하기 때문에 (또는 그에 준하는 과정을 구현해야 하기 때문에) 상대적으로 복잡하기 때문이다.

 

LSD 방식을 사용하면 자릿수가 서로 다른 수를 올바르게 정렬할 수 있다. MSD처럼 2보다 10이 먼저 오는 일은 없다. 또, LSD 정렬은 일반적으로 stable하다.

장점

조건만 맞다면 매우 빠르게 정렬할 수 있다. 가장 긴 값의 자릿수를 $W$라고 하면, 기수 정렬의 시간 복잡도는 $O(NW)$이다. 

단점

사전 순으로 늘어놓을 수 있는 값만 정렬할 수 있다. 대략 정수와 문자열 정도뿐이다. 부동소수점 실수도 (문자열로 변환하지 않는 한) 정렬 불가.

시간복잡도

$O(NW)$. $W$는 가장 긴 값의 자릿수이다.

계수 정렬 (Counting Sort)

말 그대로 값이 몇 번 나왔는지 세어 정렬한다. 1이 3번, 2가 2번, 3이 1번 나왔다면 ``1 1 1 2 2 3``을 출력하면 정렬 끝!

 

뭔가 속은 것 같다고? 어쨌든 정렬되지 않았는가?

장점

좁은 범위의 값이 매우 많이 주어지는 경우에 매우 효율적으로 정렬할 수 있다.

단점

메모리 사용량이 값의 범위에 비례하여 늘어난다. 수의 범위가 10억 미만의 자연수라면 4바이트 정수 기준 3.7GB 정도의 메모리가 필요하다.

 

정렬 특성상 정렬할 수 있는 값이 정수로 한정된다. 

시간복잡도

$O(N)$.