정렬 (기수, 계수, 셀)

기수 정렬 구현하기

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));
    }
}

1. 준비단계
   -ArrayList<Queue<Integer>> list 는 0부터 9까지의 10개의 큐를 저장. 각 큐는 해당 자릿수의 값에 해당하는 숫자를 저장

2.최대 자릿수 계산
-getMaxLen(int[] arr) 메서드는 배열에서 가장 큰 숫자의 자릿수를 계산. 이는 기수 정렬의 단계 수를 결정

3. 기수 정렬 단계
   -div변수는 현재 처리중인 자릿수의 나눗셈 기준을 나타냄. 처음에는 1의자리, 다음은 10의자리
   -외부 루프는 자릿수의 최대길이 maxLen만큼 반복
   -내부 루프에서 배열의 각 요소를 현재 자릿수에 따라 적절한 큐에 넣음
   -모든 큐의 요소를 다시 배열에 차례로 넣어 한 자릿수 단계의 정렬을 완료

4. 시간복잡도 : O(d * (n + k)) d는 자릿수, n은 요소 수, k는 기수의 크기. 배열의 요소수가 많을때 유리하게 작용하는 정렬 알고리즘

계수 정렬 구현하기

import java.util.Arrays;

public class Main2 {
    public static void countingSort(int[] arr) {
        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;
            }
        }
    }

    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));
    }
}

1. 최대값 찾기
   -Arrays.stream(arr).max().getAsInt(); 를 사용하여 배열에서 가장 큰 값을 찾음. 예제에서 최대값은 99

2. 카운팅 배열 초기화
   -int[] cntArr = new int[max + 1]; 로 최대값 99에 맞춰 길이가 100 인 카운팅 배열을 초기화

3. 카운팅 배열 채우기
   -for (int i = 0; i < arr.length; i++) { cntArr[arr[i]]++; } 로 원래 배열의 각 요소를 카운팅 배열에 인덱스로 사용하여 값을 증가. 예를들어 배열에 10이 두번 나오므로 cntARr[10] 의 값이 2가 됨

4. 정렬된 배열 생성
   -for (int i = 0; i < cntArr.length; i++) { while (cntArr[i] > 0 { arr[idx++] = i; cntArr[i]--; } } 를 사용하여 카운팅 배열의 값을 순서대로 원래 배열에 채움

5. 시간복잡도 : O(n + k) n은 배열의 길이, k는 배열의 최대값. k가 n에 비해 작거나 비슷한 경우 효율적. k가 매우 클 경우 메모리 사용량이 증가하게 되어 비효율

계수정렬을 HashMap으로 구현

HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : arr) {
            map.put(i, map.getOrDefault(i, 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--;
            }
        }

1. 해시맵을 사용하여 요소의 빈도수 계산
   -map.put(i, map.getOrDefault(i, 0) + 1); 을 통해 배열의 각 요소를 키로 하여 해시맵에 저장하고, 값으로 해당 요소의 빈도수를 저장.
   map.getOrDefault(i, 0) 은 키 i가 존재 하면 그 값을 반환하고, 존재하지 않으면 기본값 0 을 반환

2. 리스트에 해시맵의 키를 저장하고 정렬
   ArrayList<Integer> list = new ArrayList<>(map.keySet()); 로 해시맵의 키셋을 리스트로 변환.
   Collections.sort(list); 를 사용하여 키 리스트를 오름차순으로 정렬

3. 원본 배열에 정렬된 순서대로 값을 저장
   -정렬된 키 리스트를 순회하면서 각 키에 해당하는 빈도수만큼 원본 배열에 값을 채움.
   int cnt = map.get(list.get(i)); 로 빈도수를 가져와서 while (cnt > 0) 을 통해 값을 채워넣음

셀 정렬 구현하기

import java.util.Arrays;

public class Main3 {

    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;
            }
        }
    }

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

1. 초기 간격 설정
   -int gap = arr.length / 2; 로 배열의 길이의 절반을 초기 간격으로 설정

2. 간격을 줄여가며 정렬 수행
   -for (int g = gap; g > 0; g /=2) 는 간격을 절반으로 줄여가며 반복
   -내부루프에서는 for (int i = g; i < arr.length; i++) 로 현재 간격에 대해 삽입 정렬을 수행
   -while (k >= g && arr[j - g] > tmp) 는 현재 요소를 이전 간격에 있는 요소들과 비교하여 삽입 위치를 찾음

3. 간격이 1이 될 때까지 반복
   -최종적으로 간격이 1이 되면 전체 배열에 대해 삽입 정렬을 수행하여 정렬을 완료

4. 시간복잡도 : O(n log n) 에서 O(n^2) 사이로, 간격 시퀀스에 따라 성능이 달라질 수 있음. 일반적으로 삽입정렬에 비해 더 효율적이며, 특히 데이터가 어느정도 정렬된 경우 더 좋은 성능을 보임