정렬3 (기수정렬, 계수정렬, 쉘정렬)

1. 기수 정렬 (Radix Sort)

• 낮은 자리 수 부터 정렬하는 방식
• 각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이브을 위한 메모리 필요
• 알고리즘 복도 : O(dn) (d: 최대 자릿수)

1) 1의 자리 숫자 기준으로 먼저 정렬

2) 10의 자리 숫자 기준으로 정렬

// 알고리즘 - 정렬_3
// 기수 정렬

// int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
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;
    }

2. 계수 정렬

• 숫자 끼리 비교하지 않고 카운트를 세서 정렬하는 방식
• 카운팅을 위한 메모리 필요
• 알고리즘 복잡도 : O(n + k) (k: 정렬 대상 데이터 중 최대값)

// int[] arr = {10, 32, 10, 27, 32, 17, 99, 56};
public static void countingSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int[] cntArr = new int[max+1];
        int idx = 0;

        for (int ele : arr) {
            cntArr[ele]++;
        }

        for (int i = 1 ; i <= max ; i ++) {
            if (cntArr[i] != 0) {
                for (int j = 0 ; j < cntArr[i] ; j++) {
                    arr[idx++] = i;
                }
            }
        }
    }

3. 쉘 정렬

• 삽입 정렬의 약점 보완한 정렬 방식
• 삽입 정렬의 약점
  • 오름 차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 모두 교환 필요
• 이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교
• 알고리즘 복잡도 : O(n^2)
  • 간격 설정에 따라 Worst case는 삽입 정렬과 동일
  • 일반적인 선포 데이터 기준으로는 삽입 정렬에 비해 빠르다

// int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
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++) {
                int tmp = arr[i];

                int j = 0;
                for (j = i - g ; j >= 0 ; j -= g) {
                    if (arr[j] > tmp) {
                        arr[j + g] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j + g] = tmp;
            }
        }
    }

4. 정렬 별 시간 복잡도 정리