[Algorithm] 기수 정렬

Idea

 

기수 정렬은 맨 뒤에 있는 자릿수부터 해당 자릿수를 기준으로 정렬한 뒤, 앞으로 이동하며 각 자리 수를 기준으로 정렬하다가 최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법이다.

 

[823, 916, 423, 840, 268]을 기수 정렬을 이용해서 정렬해보겠다.

https://rninche01.tistory.com/entry/정렬-알고리즘-05-계수-및-기수-정렬Counting-Sort-Radix-Sort

 

가장 낮은 1번째 자리(1의 자리)부터 가장 높은 3번째 자리(100의 자리) 순으로 정렬한다.

 

https://visualgo.net/en 사용

 

첫 번째로 가장 낮은 자리인 1의 자리 수를 기준으로 버킷에 넣는다.

0 ~ 9 까지 버킷 번호에 각 숫자들이 자리를 찾아 배치되고 정렬되어 나온다.(버킷 내에서 정렬되는 것이 아님)

이렇게 1의 자리수를 오름차준으로 정렬하여 [0, 3, 3, 6, 8]이 되고, 이를 기준으로 계수를 정렬하면 [840, 823, 423, 916, 268]으로 정렬되는 것을 확인할 수 있다.

3에 423과 823의 두 개의 데이터가 들어간다. 이와 같이 하나의 버킷에 둘 이상의 데이터가 들어가는 경우, 각 버킷은 큐(FIFO) 자료구조를 사용하기 때문에 먼저 들어간 데이터가 먼저 꺼내어진다.

 

아래와 같이 10의 자리와 100의 자리에서도 동일한 정렬을 반복하여 정렬을 완료한다.

https://visualgo.net/en 사용

 

기수 정렬의 장단점

장점

• 비교 작업을 수행하지 않고 선형 시간 복잡도를 가지기 때문에 대규모 데이터 세트에 대한 퀵 정렬 및 병합 정렬과 같은 비교 기반 정렬 알고리즘보다 빠르다.
• 동일한 키 값을 가진 요소는 정렬된 출력에서 상대적 순서를 유지하는 안정적 알고리즘이다.
• 고정 크기를 사용하기 때문에 많은 수의 정수나 문자열을 저장하는 데 매우 효율인 알고리즘이다.
• 접미사 배열 구성 알고리즘에서 사용되고, 요소가 작을수록 효율적이다.

단점

• 실수와 같은 특수한 비교 연산이 필요한 데이터를 정렬할 때는 비효율적이다.
• 많은 양의 메모리가 필요하다.
• 소규모 데이터 셋이나 고유 키 수가 적은 데이터 셋에서는 효율적이지 않으며 길이가 다른 데이터들을 대상으로는 추가 작업이 필요하므로 사용하기 어렵다. → 사용할 수 있는 데이터에 한계를 가짐
• 버킷의 개수가 정해져 있지 않다. 따라서 데이터의 크기에 따라 더 많은 메모리를 소모할 수 있다.
• 숫자나 문자를 기반으로 하므로 전체 데이터를 미리 알아야 한다. → 유연성이 떨어짐

Code

import java.util.Arrays;
import java.util.ArrayList;

public class Main {
    public static final int MAX_DIGIT = 10; // 최대 자릿수는 10으로 설정(0에서 9까지의 숫자)
    public static int[] arr = {823, 916, 423, 840, 268}; // 정렬할 배열 초기화

    public static void radixSort() {
        int p = 1; // 자릿수를 결정하는 변수 (1의 자리, 10의 자리, 100의 자리 등) -> 현재 1의 자리수
        for(int pos = 0; pos < arr.length; pos++) { // 자릿수만큼 반복
            ArrayList<Integer>[] bucket = new ArrayList[MAX_DIGIT]; // 각 자릿수의 숫자에 따라 값을 저장할 버킷 배열
            for(int i = 0; i < MAX_DIGIT; i++)
                bucket[i] = new ArrayList<>(); // 각 자릿수 버킷을 ArrayList로 초기화

            for(int i = 0; i < arr.length; i++) { // 모든 배열 요소를 순회
                int digit = (arr[i] / p) % 10; // 현재 p 자릿수의 숫자 추출
                bucket[digit].add(arr[i]); // 추출된 숫자에 해당하는 버킷에 요소 추가
            }

            int index = 0; // 배열에 다시 저장하기 위한 인덱스 초기화
            for(int i = 0; i < MAX_DIGIT; i++) // 모든 버킷 순회
                for(int j = 0; j < bucket[i].size(); j++) // 각 버킷의 요소들을
                    arr[index++] = bucket[i].get(j); // 원래 배열로 다시 저장

            p *= 10; // 다음 자릿수로 이동
        }
    }

    public static void main(String[] args) {
        System.out.println("정렬 전 : " + Arrays.toString(arr));
        radixSort(); // 기수 정렬 실행
        System.out.println("정렬 후 : " + Arrays.toString(arr));
    }
}

Time Complexity

기수 정렬은 가장 작은 자리수 부터 큰 자리수까지 숫자들을 0~9까지 숫자로 정렬하는 것을 반복하면 정렬된 결과를 얻을 수 있다. 따라서 기수 정렬의 시간복잡도는 O(k * n)으로, 여기서 k는 자릿수(가장 긴 자릿수)를 의미고, n은 요소의 수를 의마한다. 각각의 데이터에 대해 자릿수마다 분류 작업을 하기 때문에 이러한 작업이 k번 반복된다고 할 수 있다.

 

 

[출처]

https://rninche01.tistory.com/entry/정렬-알고리즘-05-계수-및-기수-정렬Counting-Sort-Radix-Sort

[정렬 알고리즘] 05 계수 및 기수 정렬(Counting Sort / Radix Sort) 이론 및 구현

https://velog.io/@https00200/algorithm-radixSort