[알고리즘] O(N)의 시간복잡도를 가지는 계수 정렬(Counting Sort)와 기수 정렬(Radix Sort)

수영·2022년 10월 30일

sorting 알고리즘

알고리즘

목록 보기

10/14

정렬 알고리즘의 시간복잡도

지금껏 우리가 사용하고 있던 정렬 알고리즘의 시간복잡도는 보통 $O(N^2)$ 과 $O(NlogN)$ 입니다.

두 개의 각 시간복잡도를 가지는 정렬 알고리즘의 종류는 아래👇와 같습니다.

$O(N^2)$ 의 시간복잡도를 가지는 정렬 알고리즘

삽입 정렬(Insertion Sort)
선택 정렬(Selection Sort)
버블 정렬(Bubble Sort)

$O(NlogN)$ 의 시간복잡도를 가지는 정렬 알고리즘

퀵 정렬(Quick Sort)
힙 정렬(Heap Sort)
병합 정렬(Merge Sort)

위의 정렬 알고리즘들은 모두 다른 수와의 비교를 통해서 주어진 수를 정렬합니다.

하지만, 비교를 하지 않고 정렬을 하게 되면 $O(N)$ 의 시간복잡도를 가지는 알고리즘을 만들어 낼 수 있습니다.

🙋‍♀️ : 네?! 비교를 하지 않고 정렬을 할 수 있다구요?

👩‍🏫 : 물론입니다! $O(N)$ 의 시간으로 정렬을 할 수 있는 계수 정렬(Counting Sort)와 기수 정렬(Radix Sort)에 대해서 알아봅시다.

계수 정렬(Counting Sort)이란?

💡 Counting Sort의 기본 아이디어

말 그대로 'Counting'해서 정렬하는 방식입니다.

👆 위와 같은 수들을 정렬해야 한다고 생각해봅시다.

각 수 별로 몇 번 등장하는지를 Counting해보면 아래와 같습니다.

0 : 2번
2 : 2번
3 : 3번
5 : 1번

이걸 순서대로 나열해보면, 0, 0, 2, 2, 3, 3, 3, 5로 잘 정렬이 됩니다.

이게 Counting Sort의 기본적인 아이디어입니다!

실제로 어떻게 구현이 되는지 자세히 확인해봅시다.

🧐 Counting Sort의 과정

Counting Sort는 아래와 같은 과정을 거쳐서 정렬이 이루어집니다.

입력받은 배열 A와 각 숫자들의 등장 횟수를 담을 배열 B, 최종적인 정렬 결과를 담을 배열 C를 준비합니다.
A에서 등장하는 숫자들을 B의 인덱스로 접근하여 해당 값을 1씩 증가해줍니다.
B가 계산이 되면, 앞에서부터 누적합을 계산하여 값을 바꾸어줍니다.
A의 뒤에서부터 숫자를 확인하며 해당 숫자를 B의 인덱스로 접근하여 누적합을 확인하고, 누적합을 통해 자신이 정렬을 했을 때의 몇 번째 숫자인지를 확인하여 C의 알맞은 자리에 숫자를 넣어줍니다. 그리고 해당 누적합을 하나 줄여줍니다.
A의 모든 값들을 확인할 때까지 이를 반복합니다.

📖 Counting Sort의 예시

예시를 통해 좀 더 쉽게 이해해 봅시다!

위와 같은 세 배열이 있습니다.
우리는 A의 숫자들을 정렬해야 합니다.

우선, A 배열의 숫자들이 등장하는 횟수를 B배열에 저장합니다.

0의 경우 2번 등장하기 때문에 B 배열의 인덱스 0에 2를 저장해줍니다. 나머지 2, 3, 5도 동일하게 Counting하여 저장해주면 됩니다!

그리고 B 배열의 값을 누적합으로 바꾸어줍니다.
➡ B[i + 1] += B[i]

B 배열의 누적합 계산이 끝나면, A 배열의 뒤에서부터, 값을 확인합니다.

이 경우, 숫자는 3이기 때문에 B 배열의 인덱스 3에 접근합니다. 값이 7이라는 뜻은 숫자가 정렬되었을 때 일곱번째 순서가 된다는 의미입니다.

따라서, 정렬된 배열 C의 일곱번째 순서에 3을 넣어줍니다.

확인했던 B배열의 인덱스 3의 값은 1 줄여 6으로 바꾸어 줍니다.

그리고 A 배열의 다음 숫자를 확인합니다. 숫자가 0이기 때문에 B 배열의 0번째 인덱스를 확인하고, 값이 2이므로 C 배열의 두번째 순서에 0을 넣어줍니다.

확인했던 B배열의 인덱스 0의 값은 1 줄여 0으로 바꾸어 줍니다.

그리고 A 배열의 다음 숫자를 확인합니다. 숫자가 또 다시 3이기 때문에 B 배열의 3번째 인덱스를 확인하고, 값이 6이므로 C 배열의 여섯번째 순서에 0을 넣어줍니다.

이런 식으로 반복하다보면, 모든 수를 정렬할 수 있습니다!

⏰ Counting Sort의 시간복잡도

$O(N + k)$

카운팅을 하는 과정과, 다시 입력 배열을 뒤에서 부터 확인하는 과정이 모두 $O(N)$ 입니다.
$k$ 는 정렬해야 하는 숫자들 중 최댓값을 의미합니다. 누적합을 구하는 과정이 $O(k)$ 가 됩니다.
따라서, $k < N$ 이라면, 시간복잡도는 $O(N)$ 이 될 수 있습니다.

📚 Counting Sort의 특징

Counting Sort는 입력 배열의 동일한 값이 출력 배열의 동일한 순서로 나타나는 안정(stable) 정렬 방식입니다.
카운팅을 위한 배열의 길이가 정렬해야 하는 숫자들 중의 최댓값인 $k$ 에 의해 결정이 됩니다.
➡ 만약, [1, 1000]의 배열을 정렬해야 한다면, 값이 두 개임에도 불구하고 카운팅을 위한 배열의 길이는 1000을 설정되어야 합니다.
$k$ 가 $O(N)$ 인 경우에만 효율적으로 동작합니다.
음수나 소수인 경우 정렬이 불가능하며, 모든 숫자가 양수인 경우에만 정렬이 가능합니다.

기수 정렬(Radix Sort)이란?

💡 Radix Sort의 기본 개념

이번에는 $O(N)$ 의 시간복잡도를 가지는 두 번째 알고리즘인 기수 정렬(Radix Sort)에 대해서 살펴보도록 하겠습니다!

'기수'란 '자릿수'를 의미합니다.
따라서 기수 정렬(Radix Sort)란, 데이터의 각 자릿수를 낮은 자리수에서부터 가장 큰 자리수까지 올라가면서 정렬을 수행하는 것이라고 할 수 있습니다.

🧐 Radix Sort의 과정

Radix Sort는 아래와 같은 과정을 거쳐서 정렬이 이루어집니다.

정렬해야 하는 숫자들이 가지는 가장 큰 자릿수를 파악합니다.
숫자들의 1의 자릿수를 비교하며 같은 자릿수를 가진 숫자들끼리 모아줍니다.
➡ 이 때, 같은 자릿수에 여러 데이터가 있는 경우에는 입력된 순서로 숫자들을 모아줍니다.
➡ 1의 자릿수 비교가 끝나면, 1의 자리가 가장 작은 숫자들부터 가장 큰 숫자들 순으로 정렬됩니다.
다음으로 숫자들의 10의 자릿수를 비교하며 같은 자릿수를 가진 숫자들끼리 모아줍니다.
1번에서 파악한 가장 큰 자릿수까지 반복하며 숫자들의 자릿수를 비교한 뒤 모아주면 정렬이 완료됩니다.

📍 이 때, 가장 작은 자릿수부터 비교하는 방법을 LSD(Least-Significant-Digit),가장 큰 자리수부터 비교하는 방법은 MSD(Most-Significant-Digit)라고 합니다.

Radix Sorting은 LSD와 MSD 둘 다 가능하지만, 주로 LSD를 사용하기 때문에 LSD를 위주로 설명하도록 하겠습니다.