[Algorithm] 기수 정렬 (Radix Sort)

기수 정렬 (Radix Sort)

다른 정렬은 많이 들어보았는데 기수 정렬은 생소하다!

기수 개념 : ??

 

기수 정렬 (radix sort) : 낮은 자리수부터 비교하는 정렬 알고리즘이다.

비교 연산을 하지 않아 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.

 

1. 기수만큼 큐를 이용해 저장공간을 생성한다.

2. 데이터의 1의 자리가 같은 숫자들끼리 저장공간에 넣는다.

3. 저장공간에 저장된 데이터를 순서대로 꺼내 기존 데이터에 덮어쓴다.

4. 데이터의 10의 자리를 기준으로 저장공간에 넣는다.

5. 마지막 자리수까지 정렬의 기준이 될 자리수를 늘리며 정렬한다.

 

(이미지 찾는중...)

기수 정렬 (Radix Sort)의 시간 복잡도

기수 정렬은 데이터의 삽입과 추출의 빈도수로 성능을 평가한다.

길이가 가장 긴 자리수를 k, 데이터의 개수를 n일때, k 자리수까지의 반복하고 데이터 n개를 반복해서 정렬하므로 k * n이 된다. 따라서 기수 정렬의 시간복잡도는 O(kn)이다.

 

기수 정렬 (Radix Sort)의 구현

import java.util.LinkedList;
import java.util.Queue;

public class Main {
	
    static final int bucketSize = 10;
    
    public static void main(String[] args) {
    	int[] arr = {28, 93, 39, 81, 62, 72, 38, 26};
        
        radixSort(arr.length, arr);
        
        printArray(arr);
    }
    
    public static void radixSort(int n, int[] arr) {
    	// 저장공간 초기화
        Queue<Integer>[] bucket = new LinkedList[bucketSize];
        for (int i = 0; i < bucketSize; ++i) {  // ++i 를 사용한 이유?? (생각)
        	bucket[i] = new LinkedList<>();
        }
        
        int factor = 1;
        
        // 자릿수의 크기만큼 반복
        for (int k = 0; k < 2; ++k) {
        	for (in i = 0; i < n; ++i) {
            	bucket[(arr[i] / factor) % 10].add(arr[i]));
             }
             
             for (int i = 0; j = 0; i < bucketSize; ++i) {
             	while (!bucket[i].isEmpty()) {
                	arr[j++] = bucket[i].poll();
                }
             }
             
             factor += 10;
        }
    }
    
    
    public static void printArray(int[] arr) {
    	for (int i = 0; i < arr.length; i++) 
        	System.out.print(a[i] + " ");
        System.out.println();
    }
    
}

 

 

출처 

https://lktprogrammer.tistory.com/48

https://banjjak1.tistory.com/52

https://sorjfkrh5078.tistory.com/21