정렬

정렬은 컴퓨터과학 분야에서 광범위하게 사용되는 개념입니다.

데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미하는데, 오름차순, 내림차순, 등등 상황에 따른 여러 특정한 기준이 존재합니다.

다양한 정렬 알고리즘이 존재하며, 각각 장점과 단점을 가지고 있습니다. 이 중 상황에 맞는 효율적인 알고리즘을 고르는 것이 중요합니다.

다음과 같은 숫자가 있다고 생각합시다:

7, 5, 9, 0, 3, 1, 6, 2, 4, 8

우리는 위 숫자들을 오름차순으로 정렬하고 싶습니다. 어떻게 진행할까요?

전체 숫자를 슥 보고, 숫자들이 0~9 사이의 숫자들임을 파악한 후, 0부터 차례대로 나열할 것입니다.

하지만 컴퓨터가 정렬을 할 때도 이런 방법이 효율적일까요? 또, 데이터가 수백, 수천만 개가 있다면 이런 방법이 효율적일까요?

위와 같은 상황들을 고려하여 적합한 알고리즘들이 이미 연구되어 있습니다.

여기서는 다음 정렬 알고리즘을 다루고자 합니다. 모두 오름차순으로 정렬한다고 가정합니다.

선택 정렬 (Selection sort)
삽입 정렬 (Insertion sort)
퀵 정렬 (Quick sort)
계수 정렬 (Count sort)

선택 정렬

선택 정렬 (selection sort)는, 가장 원시적은 정렬 알고리즘으로, '가장 작은 수를 선택' 하는 알고리즘입니다.

데이터가 무작위로 여러 개 있을 때, 이들 중 가장 작은 데이터를 선택하여 맨 앞의 수와 바꾸고 (swap), 그 다음으로 작은 데이터를 선택하여 2번째 자리의 수와 바꾸고... 를 반복합니다.

데이터의 개수를 N으로 나타냅니다. N = 10일 때, 정렬하는 예를 보겠습니다.

파란색은 이미 정렬된 수, 빨간색은 다음 바꿀 대상으로 선정된 수를 의미합니다.

매번 정렬되지 않은 수 (검정색)들을 끝까지 탐색한 후, 가장 작은 숫자를 빨간색으로 지정한 다음,

첫 번째 검정색 수와 자리를 바꿉니다.

선택 정렬의 시간 복잡도를 구해 봅시다.

1번째 단계에서 10번째 단계까지, 총 N번 숫자 바꾸기가 일어납니다.

또, 매회 가장 작은 숫자를 찾기 위해 비교 연산을 수행하는데, 이 횟수는 (N-1) + (N-2) + ... + 2 번 일어납니다.

근사하여 (N + 1) / 2번의 비교 연산이 수행됩니다.

따라서 알고리즘 전체의 시간 복잡도는 N * (N + 1) / 2 = O(N^2)라고 할 수 있습니다.

비유하자면, 약 1만 개의 데이터를 정렬해야 한다면, 최악의 경우 1억 번의 연산을 해야 합니다.

선택 정렬은 구조가 매우 간단한 만큼, 다른 비교 알고리즘에 비해 매우 비효율적인 알고리즘입니다.

다음 표를 참고하시면 이를 체감할 수 있습니다.

데이터의 개수 (N)	선택 정렬 (s)	퀵 정렬 (s)	파이썬 기본 정렬 라이브러리 (s)
100	0.0123	0.00156	0.00000753
1000	0.354	0.00343	0.0000365
10000	15.475	0.0312	0.000248

(표 출처: "나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 2020), p161")

선택 정렬이 얼마나 비효율적인지 체감이 되시나요?

N = 10000 즈음부터 선택 정렬은 급속도로 정렬 속도가 느려지는 것을 확인할 수 있습니다.

다만, 코딩 테스트에서 특정한 데이터 목록 중에서 가장 작은 데이터를 찾는 일이 종종 있으므로, 선택 정렬의 알고리즘에 익숙해질 필요가 있습니다.

삽입 정렬

삽입 정렬 (insertion sort)는 '데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다' 는 아이디어에 기반한 정렬 알고리즘입니다.

여기서 적절한 위치는 두 수의 비교를 통해 정해집니다.

예를 들어 숫자 1, 4, 6이 있고, 3을 적절한 위치에 삽입한다고 가정해 봅시다.

가능한 위치는 총 4개입니다. 1의 왼쪽, 1, 4의 사이, 4, 6의 사이, 6의 오른쪽.

가장 오른쪽의 숫자인 6과 제일 먼저 비교합니다. 3이 6보다 작으므로, 3은 6의 왼쪽으로 갑니다.

그 다음 숫자인 4와 비교합니다. 3이 4보다 작으므로, 3은 4의 왼쪽으로 갑니다.

그 다음 숫자인 1과 비교합니다. 3이 1보다 크므로, 3은 1과 4 사이에 삽입합니다.

위 과정이 삽입 정렬의 기본적인 아이디어입니다.

이를 바탕으로, N = 10일 때 숫자를 정렬하는 과정을 예시로 보여 드리겠습니다.

빨간색은 기준으로 한 숫자를 삽입한 것, 파란색은 이미 삽입되어 졍렬된 수, 검정색은 아직 정렬되지 않은 수입니다.

첫 단계는 이미 숫자 1개가 정렬되어 있다고 보고, 이후에 숫자를 적절한 위치에 삽입하는 과정을 N = 1에서 N = 9까지, 총 N-1회 반복하게 됩니다.

이미 정렬된 파란색 숫자를 보시면, 숫자들이 이미 정렬되어 있으므로 적당한 위치를 찾으면 더 이상 비교 연산을 할 필요가 없습니다.

N = 6일 떄, 6이 5보다 크고 7보다 작으므로, 5보다 작은 이미 정렬된 숫자인 0, 1, 3과는 비교할 필요가 없는 것입니다.

삽입 정렬 역시 선택 정렬과 마찬가지로 O(N^2)의 시간 복잡도를 가집니다. 반복문이 2번 중첩되어 있기 때문입니다.

삽입 정렬의 특징은, 정렬하려는 숫자의 목록이 이미 정렬이 되어 있는 상태라면, 매우 빠르게 동작합니다.

최선의 경우, O(N)의 시간 복잡도를 가집니다. 따라서, 숫자 목록이 이미 정렬이 되어 있는 등 특정한 상황에서는, 삽입 정렬을 사용하는 것이 적합합니다.

퀵 정렬

퀵 정렬 (quick sort)은 현재 아주 대중적으로 사용되고 있는 알고리즘입니다. 그만큼 효율적이고 빠른 알고리즘인데, 이와 비슷한 알고리즘으로는 오늘 다루지는 않지만 병합 정렬 (merge sort)이 있습니다. 이 두 알고리즘이 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 됩니다.

기본적인 아이디어는 "기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터를 서로 교환한다" 입니다.

기준 데이터를 정한 후, 리스트를 반으로 나누는 동작 방식을 가집니다.

앞서 소개한 정렬 알고리즘보다 조금 복잡하지만, 그만큼 이해하면 쉽게 사용할 수 있습니다.

과정을 나누기에 앞서, 퀵 정렬은 늘 리스트에서 첫 번째 데이터를 피벗 (기준점) 으로 정합니다.

이번에는 5, 7, 9, 0, 3, 1, 6, 2, 4, 8을 정렬하는 것을 예로 들겠습니다.

단계 1

맨 왼쪽 숫자가 피벗이 됩니다. 이를 초록색으로 표시하였습니다.

피벗을 제외하고, 맨 왼쪽부터 차례로 숫자를 검사하여 피벗보다 숫자가 큰 경우를 찾습니다. 이를 빨간색으로 표시하였습니다.

맨 오른쪽부터 차례로 숫자를 검사하여 피벗보다 숫자가 작은 경우를 찾습니다. 마찬가지로 빨간색으로 표시하였습니다.

위에서 고른 두 숫자의 자리를 서로 바꿉니다. 이미 자리를 바꾼 숫자들은 파란색으로 표시하였습니다.

위 과정을, 두 빨간색이 교차할 때까지 반복합니다. 위 예에서, 가장 처음 찾은 5보다 큰 수는 6이며, 가장 처음 찾은 5보다 작은 수는 1입니다. 서로 교차했음을 확인할 수 있습니다.

교차하는 때, 더 작은 숫자와 피벗의 위치를 서로 교환합니다.

그러면, 피벗을 기준으로 위와 같은 결과를 얻을 수 있습니다.

피벗을 기준으로 좌측에는 피벗보다 작은 숫자들이, 우측에는 피벗보다 큰 숫자들이 모여 있습니다.

단계 2

피벗을 기준으로 좌측 부분 리스트에 대해 단계 1을 수행합니다. 위의 경우, 피벗은 1이 되며, 1을 기준으로 좌측은 1보다 작은 숫자, 우측은 1보다 큰 숫자가 모이게 됩니다.

단계 3

피벗을 기준으로 우측 부분 리스트에 대해 단계 1을 수행합니다. 위의 경우, 피벗은 6이 되며, 6을 기준으로 좌측은 6보다 작은 숫자, 우측은 6보다 큰 숫자가 모이게 됩니다.

자세히 보시면 퀵 정렬은 재귀함수의 형태를 띄게 됨을 알 수 있습니다. 부분 리스트를 기준으로 하여 더 작은 부분 리스트가 2개 생성되고, 생성된 부분 리스트를 기준으로 하여 더더욱 작은 부분 리스트가 생성되고... 가 반복됩니다.

이는 리스트에 숫자가 1개만 남을 때까지 반복됩니다. 숫자가 1개뿐이라면, 이미 정렬이 되었다고 가정하며 분할할 수 없습니다.

초록색은 피벗, 밑줄 친 숫자는 해당 피벗이 포함된 부분 리스트, 파란색은 이미 정렬된 숫자입니다.

퀵 정렬은 평균 O(N log N)의 시간 복잡도를 가집니다. 앞서 다루었던 삽입 정렬, 선택 정렬에 비해 속도가 매우 빠른 편입니다.

간단히 이를 설명하자면, 데이터가 N개 존재할 때, 정렬이 일어나는 횟수가 log N 번이 됩니다. 이때 log는 평균적으로 베이스를 2로 가집니다.

물론 최악의 경우, 정렬이 일어나는 횟수가 N에 가까워지면, O(N^2)의 시간 복잡도를 가지게 됩니다. 이는 숫자들이 대부분 정렬된 상태로 시작하는 경우 발생합니다.

계수 정렬

계수 정렬 (count sort)은 특수한 정렬 알고리즘입니다.

"데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때" 사용하는 매우 빠른 알고리즘입니다.

예를 들어 데이터의 개수가 N, 데이터의 최댓값이 K라면, 최악의 경우에도 수행시간 O(N+K)가 보장됩니다.

예를 들어, 0~100 사이의 성적 데이터를 정렬하는 경우, 값이 정수이고 최댓값이 100으로 정해져 있으므로 계수 정렬을 사용할 수 있습니다. 하지만, 만약 0~1억 사이의 데이터를 정렬하는 경우 계수 정렬은 사용할 수 없습니다.

계수 정렬은 모든 범위를 담을 수 있는 크기의 배열을 미리 선언해야 합니다. 가장 큰 데이터와 작은 데이터의 차가 100만이라면, 총 100만 1의 크기를 가지는 배열이 필요합니다 (0 ~ 1,000,000).

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 를 정렬한다고 가정해 봅시다. N = 15, K = 9이며, 가장 작은 숫자는 0입니다.

따라서, (9 - 0) + 1 = 10의 크기를 가지는 배열을 생성합니다.

정렬을 하려는 숫자를 대상으로, 앞에서부터 각 숫자를 확인하고 숫자가 나온 횟수만큼 값을 배열의 인덱스에 누적합니다.

위 예시와 같이 과정을 반복하고 나면, 각 숫자들의 등장 횟수가 기록이 됩니다.

다음으로, 각 숫자의 횟수만큼 출력을 해 주면 정렬된 결과를 얻을 수 있습니다.

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

계수 정렬은 앞서 말한 것처럼 시간복잡도는 매우 우수합니다. O(N+K)의 시간 복잡도를 가지므로, 매우 빠른 정렬 결과를 보일 수 있습니다.

하지만 계수 정렬은 공간 복잡도 또한 고려해야 합니다. N의 크기가 매우 크면, 그만큼 배열을 크게 생성해야 하므로, 메모리 사용량이 매우 커질 수 있습니다. 만약 1, 999999, 19940294245 세 숫자를 정렬한다면, 계수 정렬은 매우 비효율적인 방법이 될 것입니다.

계수 정렬은 배열의 크기가 100만 이하일 때 대체로 효율적으로 동작하는 편인데, 코딩 테스트에서의 데이터 개수는 보통 1000만 개 이하인 편입니다. 알아두면 유용하게 사용할 수 있을 것입니다.

정렬 알고리즘을 몇 개 다루었지만, 보통 직접 코딩할 때는 정렬 라이브러리를 사용하게 됩니다. 제가 주로 사용하는 C++와 Python 모두 아주 우수한 효율의 정렬 라이브러리가 포함되어 있습니다. 하지만, 정렬 알고리즘은 기술면접 등에서 나오는 경우도 있으므로, 알고리즘을 잘 이해하고 언제든 코드로 나타낼 수 있어야 합니다.

*본 글은 "나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 2020)" 를 참고하여 작성하였습니다.