기수 정렬(Radix sort)과 계수 정렬(Counting sort)

기수 정렬

• 낮은 자리 수부터 정렬하는 방식
• 각 원소간의 비교연산을 하지 않아 빠른 대신, 기수 테이블을 위한 메모리가 필요하다.
• 장점 : 문자열과 정수를 정렬할 수 있다.
• 단점 : 자릿수가 없는것은 정렬할 수 없다.
• 알고리즘 시간 복잡도 : O(dn) - d는 최대 자리 수
  

질문

• 왜 낮은 자리수부터 정렬을 할까?
  • MSD(Most-Significant-Digit)과 LSD(Least-Significant-Digit)을 비교
  • MSD는 가장 큰 자리수 부터 정렬하는 것을 의미하고, LSD는 가장 낮은 자리수부터 정렬하는 것이다. 즉, 둘다 가능하다!
  • LSD의 경우 1600000 과 1을 비교할 때, Digit의 갯수만큼 따져야하는 단점이 있다. 그에 반해 MSD는 마지막 자리수까지 확인해 볼 필요가 없음.
  • LSD는 중간에 정렬 결과를 알 수 없음. (예) 10004와 70002의 비교) 반면, MSD는 중간에 중요한 숫자를 알 수 있음. 따라서 시간을 줄일 수 있음. 그러나, 정렬이 되었는지 확인하는 과정이 필요하고, 이 때문에 메모리를 더 사용
  • LSD는 알고리즘이 일관됨 (Branch Free algorithm) 그러나 MSD는 일관되지 못함.
  • 따라서 Radix sort는 주로 LSD를 언급함.
  • LSD는 자릿수가 정해진 경우 좀 더 빠를 수 있음.

// 기수 정렬

import javax.management.QueryEval;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void radixSort(int[] arr) {
        // 기수 테이블 생성
        ArrayList<Queue<Integer>> list = new ArrayList<>();
        for(int i = 0; i<10; i++){
            list.add(new LinkedList<>());
        }

        int idx= 0;
        int div= 1;
        int maxLen = getMaxLen(arr);
        // 자리수 만큼 기수 정렬 반복
        for(int i = 0; i<maxLen; i++){
            // 각 자리수에 맞는 큐 위치에 데이터 삽입
            for(int j = 0; j<arr.length; j++){
                list.get((arr[j]/div)%10).offer(arr[j]);
            }

            // 다시 순서대로 가져와서 배치
            for(int j = 0; j<10; j++){
                Queue<Integer> queue = list.get(j);

                while(!queue.isEmpty()){
                    arr[idx++] = queue.poll();
                }
            }
            idx = 0;
            div *= 10;
        }

    }

    public static int getMaxLen(int[] arr){
        // 배열의 숫자 중 가장 큰 자리수 구하기
        int maxLen = 0;
        for(int i = 0; i<arr.length; i++){
            int len =(int)Math.log10(arr[i])+1;
            if(maxLen<len){
                maxLen = len;
            }
        }
        return maxLen;
    }


    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

계수 정렬

• 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식
• 카운팅을 위한 메모리가 필요(원소의 최댓값 길이 만큼의 배열을 만들어야 함)
• 알고리즘 복잡도 : O(n + k) - k는 정렬 대상 데이터 중 최댓값
• 사용 : 정렬하는 숫자가 특정한 범위 내에 있을때 사용
• 장점 : O(n)의 시간 복잡도
• 단점 : 카운팅 배열의 사용으로 메모리 낭비가 심함
  

// 계수 정렬

import java.util.*;

public class Main2 {
    public static void countingSort(int[] arr) {
        // 1. 일반 배열 사용
        // 최댓값 구해서 배열 설정
        int max = Arrays.stream(arr).max().getAsInt();
        int[] cntArr = new int[max+1];

        for(int i = 0; i<arr.length; i++){
            cntArr[arr[i]]++;
        }

        int idx = 0;
        for(int i = 0; i<cntArr.length; i++){
            while(cntArr[i]>0){
                arr[idx++] = i;
                cntArr[i]-=1;
            }
        }

        // 2. 해쉬맵 사용
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int item : arr){
            map.put(item, map.getOrDefault(item, 0)+1);
        }

        int idx2 = 0;
        ArrayList<Integer> list= new ArrayList<>(map.keySet());
        Collections.sort(list);
        for(int i = 0; i<list.size(); i++){
            int cnt = map.get(list.get(i));
            while(cnt>0){
                arr[idx2++] = list.get(i);
                cnt--;
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 10, 27, 32, 17, 99, 56};
        countingSort(arr);
        System.out.println("계수 정렬: " + Arrays.toString(arr));
    }
}