선택 정렬 (Selection Sort)

• 정렬이 되어있지 않은 배열이나 리스트에서 K번째 작은(또는 큰) 원소를 찾아내는 알고리즘
• 최솟값, 최댓값, 중간값, 임의의 k번째 작은 값을 빠르게 구하고 싶을 때 사용
• 퀵 셀렉트, 정렬 후 선택
• k가 비교적 작을 때 유용
• 시간 복잡도 : O(N^2)
• 정렬 과정
  • 주어진 리스트 중 최솟값 찾기
  • 맨 앞의 원소와 가장 작은 값을 swap
  • 맨 앞의 원소를 제외한 나머지 구간에 반복 수행

public class Selection {
    public static int select(int[] nums, int k) {
        int n = nums.length;

        // 선택 정렬 알고리즘을 k번 반복
        for (int i = 0; i < k; i++) {
            int minIndex = i; // 현재 구간에서 최소값의 인덱스 초기화
            for (int j = i + 1; j < n; j++) {
                if (nums[minIndex] > nums[j]) {
                    minIndex = j; // 더 작은 값을 발견하면 minIndex 업데이트
                }
            }
            // 현재 인덱스(i)와 최소값 인덱스(minIndex) 교환
            swap(nums, i, minIndex);
        }

        // k번째 작은 값 반환
        return nums[k - 1];
    }

    // 두 배열 요소를 교환하는 메서드
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {7, 10, 4, 3, 20, 15};
        int k = 3; // k번째 작은 값 찾기

        int result = select(nums, k);
        System.out.println(k + "번째로 작은 값: " + result);
    }
}

카운팅 정렬 (Counting Sort)

• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
• 안정적 정렬로 구현 가능 (원본 순서 보존)
• 정수나 정수로 표현할 수 있는 자료에 대해서 정렬 가능
  → 각 항목의 발생 횟수를 기록하기 위해 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문
  
• 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함
• 시간 복잡도 : O(n + K ) → n은 배열의 길이, K는 정수의 최댓값

public class CountingSort {
    public static int[] countingSort(int[] A, int n, int k) {
        // 결과를 담을 배열 B 준비
        int[] B = new int[n];
        
        // 카운트 배열 초기화
        int[] count = new int[k + 1];
        
        // 카운트 배열에 각 숫자의 빈도 기록
        for (int i = 0; i < n; i++) {
            count[A[i]]++;
        }
        
        // 누적합 구하기
        for (int x = 1; x <= k; x++) {
            count[x] = count[x] + count[x - 1];
        }
        
        // 뒤에서부터 A를 확인하며 결과 B에 배치
        for (int i = n - 1; i >= 0; i--) {
            int val = A[i];
            count[val]--;
            int newIndex = count[val];
            B[newIndex] = val;
        }
        
        return B;
    }

    public static void main(String[] args) {
        // 예제 배열
        int[] A = {3, 13, 26, 88, 22, 11, 54, 12};
        int n = A.length;
        int k = 88; // A 배열의 최대값
        
        // 카운팅 정렬 호출
        int[] sortedArray = countingSort(A, n, k);
        
        // 결과 출력
        System.out.println(Arrays.toString(sortedArray));
    }
}

장점

1. 빠른 속도
   특정 조건에서(데이터의 범위 k가 작은 경우) 매우 빠름
   시간 복잡도가 O(n)으로, 비교 기반 정렬(예: 퀵 정렬 O(n log n))보다 유리할 수 있음

2. 안정 정렬
   동일한 값을 가진 데이터의 순서가 유지

3. 특정 상황에 적합
   값의 범위가 제한적인 정렬(예: 성적, 나이 등)에서 효율적

단점

1. 큰 메모리 사용
   데이터 값의 범위 k가 크다면 메모리를 많이 소비
   예) 값의 범위가 0에서 1,000,000이라면, count 배열에 1,000,001개의 공간이 필요

2. 값이 음수일 경우
   음수 값이 포함되면, 별도로 값의 범위를 변환하는 작업이 필요

3. 실제 데이터 정렬
   정렬 대상이 단순한 정수 값이 아니라 객체인 경우, 부가적인 처리가 필요

4. 데이터 분포 의존
   값이 매우 넓은 범위에 드문드문 분포되어 있다면, 비효율적
   이 경우 n보다 k가 훨씬 커져 시간과 공간 효율이 나빠질 수 있음.

카운팅 정렬이 적합한 상황

1. 데이터의 값 범위가 작은 경우
2. 정수 또는 작은 정수값으로 변환 가능한 데이터
3. 안정 정렬이 필요한 경우(예: 학생 점수 정렬, 등수 매기기 등)