특수 정렬 알고리즘(기수 정렬)

기수 정렬

 

기수 정렬은 배열 안의 데이터가 모두 n자릿수 이하의 자연수인 경우 사용 가능한 정렬이다. 일의 자릿수로 크기 비교후 정렬하고 다음은 십의 자리, 백의 자리,...해서 n자릿수까지 크기를 비교하는 독특한 정렬이다. 

시간 복잡도는 O(dn)으로 빠른 편이다.

다만 테이블이 따로 필요하다는 단점이 있다.

 

기수 정렬이 어떤 순서로 동작하는지는 아래의 영상에 나와있다.

https://youtu.be/nu4gDuFabIM

import java.io.*; 
import java.util.*; 
  
class Radix { 

    static void countSort(int arr[], int n, int exp) 
    { 
        int output[] = new int[n];
        int i; 
        int count[] = new int[10]; 
        Arrays.fill(count,0); 
  
        for (i = 0; i < n; i++) 
            count[ (arr[i]/exp)%10 ]++; 
  
        for (i = 1; i < 10; i++) 
            count[i] += count[i - 1]; 
  
        for (i = n - 1; i >= 0; i--) 
        { 
            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
            count[ (arr[i]/exp)%10 ]--; 
        } 
  
        for (i = 0; i < n; i++) 
            arr[i] = output[i]; 
    } 
  
    static void radixsort(int[] arr, int n) 
    { 
        int max = arr[0]; 
        for (int i = 1; i < n; i++) 
            if (arr[i] > max) 
                max = arr[i]; 
        for (int exp = 1; max/exp > 0; exp *= 10) 
            countSort(arr, n, exp); 
    } 

    public static void main (String[] args) 
    { 
        int[] a= {8,31,48,73,3,65,20,29,11,15};
        int n = a.length; 
        radixsort(a,n); 
        for(int i:a){
            System.out.printf("%d ",i); 
        }
    } 
} 

계수 정렬은 영어로 Counting sort라고 한다. Counting이라는 이름답게 숫자의 개수를 센 후 누적 합을 구하고, 다시 숫자를 넣어주는 방식의 정렬이다. 시간복잡도는 최상의 경우 O(k+n)로 간단하지만 숫자가 커질수록 시간 복잡도도 커지게 된다.

 

계수 정렬을 하는 방법은 1. 배열을 처음부터 끝까지 돌면서 각 요소가 몇번 나왔는지 count 배열에 저장한다.

2.count 배열을 어떤 값이 몇번 인덱스에 위치하는지 계산함

3.count 배열을 토대로 정렬함

 

class CountingSort 
{ 
    void sort(int arr[]) 
    { 
        int n = arr.length; 
  
        int output[] = new int[n];

        int count[] = new int[256]; 
        for (int i=0; i<256; ++i) 
            count[i] = 0;
  
        for (int i=0; i<n; ++i) 
            ++count[arr[i]];
  
        for (int i=1; i<=255; ++i) 
            count[i] += count[i-1]; 

        for (int i = n-1; i>=0; i--) 
        { 
            output[count[arr[i]]-1] = arr[i]; 
            --count[arr[i]]; 
        } 

        for (int i = 0; i<n; ++i) 
            arr[i] = output[i]; 
    } 

    public static void main(String args[]) 
    { 
        CountingSort ob = new CountingSort(); 
        int[] a= {8,31,48,73,3,65,20,29,11,15};
  
        ob.sort(a); 
  
         for(int i:a){
            System.out.printf("%d ",i);
        }
    } 
}