기타 정렬 - 기수, 계수, 쉘 정렬

< 개념 >

 

---

< 구현 >

1. 기수정렬

// 기수 정렬(radix sort)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class RadixSort {
    public static void radixSort(int[] arr) {
        // 0~9까지 크기인 리스트 안에 각 원소가 큐로 이루어진 기수테이블
        ArrayList<Queue<Integer>> radixTable = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            radixTable.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++) {
                // (arr[j] / div) % 10은 arr[j]의 자리수의 숫자. 즉, 기수테이블에서의 어느 위치 결정
                radixTable.get((arr[j] / div) % 10).offer(arr[j]);
            }

            // 테이블의 값으로 다시 배열에 정렬
            for (int j = 0; j < 10; j++) {
                Queue<Integer> queue = radixTable.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++) {
            // log10을 이용하여 숫자 길이 (ex. log1010 = 1 => 10은 두자리 수 이므로 + 1)
            int len = (int)Math.log10(arr[i]) + 1;
            if (maxLen < len) {
                maxLen = len;
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] arr = {10,32,52,27,48,17,99,56};
        radixSort(arr);
        System.out.println("기수 정렬: " + Arrays.toString(arr));
    }
}

 

 

 

2.  계수정렬

// 계수정렬

import java.util.Arrays;

public class CountingSort {
    public static void countingSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int[] cntArr = new int[max + 1];
        
        // counting table에 arr의 값을 위치에 맞게 삽입
        for (int i = 0; i < arr.length; i++) {
            cntArr[arr[i]]++;
        }

        // counting table을 arr로 다시 불러와 정렬
        int idx = 0;
        for (int i = 0; i < cntArr.length; i++) {
            while (cntArr[i] > 0) {
                arr[idx++] = i;
                cntArr[i] -= 1;
            }
        }
    }

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

-> arr에 있는 최대값이 너무 말도 안되게 크다면, counting table의 용량도 커져 비효율적!

so, 다른 방법으로 풀면! counting table의 자료구조를 배열 대신 HashMap으로!

 

// 계수정렬


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

public class CountingSort {
    public static void countingSort(int[] arr) {
        // 위 counting table은 안 쓰는 공간이 있어 비효율적!
        // 배열 대신 HashMap 자료구조로
        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) {
        int[] arr = {10,32,52,27,48,17,99,56};
        countingSort(arr);
        System.out.println("계수 정렬: " + Arrays.toString(arr));
    }
}

 

 

 

3.  쉘정렬

// 쉘 정렬

import java.util.Arrays;

public class ShellSort {
    public static void shellSort(int[] arr) {
        int gap = arr.length / 2;

        for (int g = gap; g > 0; g /= 2) {
            for (int i = g; i < arr.length; i++) {
                // gap으로 삽입정렬
                int temp = arr[i];
                int j = 0;
                for (j = i - g; j >= 0; j -= g) {
                    if (arr[j] > temp) {
                        arr[j + g] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j + g] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {10,32,52,27,48,17,99,56};
        shellSort(arr);
        System.out.println("쉘 정렬: " + Arrays.toString(arr));
    }
}