기수 정렬 (Radix Sor)

정렬 알고리즘

 

 

기수 정렬 Radix Sort 

기수 정렬은 숫자나 문자에서 각 자릿수 별로 정렬하여 비교 없이 정렬하는 알고리즘입니다.

자릿수 별로 정렬을 하며, 낮은 자릿수부터 높은 자릿수까지 정렬하여 정렬을 완성합니다. 

기수 정렬은 같은 값의 요소들의 순서가 정렬 후에도 유지되는 안정적인 정렬입니다.

 

시간 복잡도 : O(k(n + k))  n : 배열의 길이, k : 숫자의 최대 자릿수(기수)

 

장점

• 빠른 속도 : 데이터의 크기가 크고 자릿수가 많아질수록 효율적입니다. 
• 안정적인 정렬 : 정렬 후에도 순서가 유지됨

 

단점

• 메모리 사용량 증가 : 정렬을 할 때, 추가 메모리가 필요하며 자릿수가 크고 배열이 클수록 메모리 사용량이 큽니다.
• 제한된 사용 조건 : 자릿수가 없는 것은 정렬할 수가 없습니다. (부동 소수점)

 

 

 

작동 원리

1. 자릿수 파악 : 데이터의 가장 낮은 자릿수와 높은 자릿수를 파악합니다. 

2. 자릿수별 정렬 : 자릿수에 대해 안정적인 정렬 방법(예시 : 계수 정렬)을 사용하여 정렬합니다. 

3. 다음 자릿수 이동 : 다음 자릿수로 이동하여 정렬을 합니다. 가장 높은 자릿수에 정렬을 마치면 정렬이 됩니다. 

 

 

 

예시

170, 45, 75, 90, 802, 24, 2, 66

 

 

1. 자릿수 파악 

배열에서 가장 큰 숫자와, 작은 숫자를 찾습니다. 

가장 큰 숫자는 802이며 최대 자릿수는 3이고 가장 낮은 숫자는 2로 자릿수는 1입니다.

 

 

2. 자릿수별 정렬 

가장 낮은 자릿수(1의 자리)부터 시작하여 가장 높은 자릿수까지 순차적으로 정렬합니다. 

 

 

3. 1의 자리 정렬 

각 숫자의 1의 자리에 대해 정렬을 수행합니다.

 

결과 배열 : 170, 90, 802, 2, 24, 45, 75, 66

1의  자리 : 0, 0, 2, 2, 4, 5, 5, 6 

 

 

4. 10의 자리 정렬

각 숫자의 10의 자리에 대해 정렬을 수행합니다. (자릿수가 없는건 0으로 간주합니다.)

 

결과 배열 : 802, 2, 24, 45, 66, 170, 75, 90

10의 자리 : 0, 0, 2, 4, 6, 7, 7, 9 

 

 

5. 100의 자리 정렬

각 숫자의 100의 자리에 대해 정렬을 수행합니다.

 

결과 배열 : 2, 24, 45, 66, 75, 90, 170, 802

100의 자리 : 0, 0, 0, 0, 0, 1, 8 

 

가장 높은 자릿수에 100의 자리까지 정렬하면 전체 배열이 정렬된 걸 볼 수 있습니다. 

 

 

 

Java 코드

위의 내용을 Java 코드로 구현하면 다음과 같습니다. 

import java.util.Arrays;

/*
기수 정렬  Radix Sort

시간복잡도 : O(nk) n : 배열의 길이 k 숫자의 최대 자릿수
자릿수를 기준으로 정렬

숫자 범위가 넓거나 정렬해야 할 문자열이 길 때 효과적이다.
그러나, 추가적인 메모리를 요구하며 자릿수가 많은 데이터에 대해서는 속도가 느려질 수 있다.
 */
public class RadixSort {

  public static void main(String[] args) {
    int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
    printArray(array);
    radixSort(array);
    printArray(array);
  }

  // 기수 정렬 시작
  public static void radixSort(int[] array) {
    int n = array.length;

    // 가장 큰 숫자를 찾아 자릿수를 결정한다.
    int max = getMax(array, n);

    // 모든 자릿수에 대해 계수 정렬을 수행한다.
    for(int exp = 1; max / exp > 0; exp *= 10) {
      countSort(array, n, exp);
    }
  }

  // 가장 큰 숫자를 찾는 메소드
  static int getMax(int[] array, int n) {
    int max = array[0];
    for(int number : array) {
      max = Math.max(max, number);
    }
    return max;
  }


  // 각 자릿수마다정렬
  public static void countSort(int[] array, int n, int exp) {

    // 결과값을 저장할 배열
    int[] output = new int[n];

    // 각 자릿수에 따른 숫자의 출현 횟수
    int[] count = new int[10];
    for(int i = 0; i < n; i++) {
      count[(array[i] / exp) % 10]++;
    }

    // 누적합 계싼
    for(int i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

    // 결과 배열 생성
    for(int i = n - 1; i >= 0; i--) {
      output[count[(array[i] / exp) % 10] - 1] = array[i];
      count[(array[i] / exp) % 10]--;
    }

    // 원래 배열 결과 복사
    for(int i = 0; i < n; i++) {
      array[i] = output[i];
    }
  }


  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }

}

 

 

 

마무리

이번에는 비교하지 않는 정렬인 기수 정렬에 대해 정리했습니다.

다음에는 비교 정렬인 퀵 정렬, 병합 정렬, 힙 정렬에 대해 정리하겠습니다.

감사합니다.