정렬

병합 정렬

import java.util.Arrays;

class MergeSort {
    public static void sort(Comparable[] arr, int left, int right) {
        if (right - left < 2) { // 조건 수정
            return;
        }
        int mid = (left + right) / 2; // 세미콜론 추가
        sort(arr, left, mid);
        sort(arr, mid, right);
        merge(arr, left, mid, right); // 세미콜론 추가
    }

    private static void merge(Comparable[] arr, int left, int mid, int right) {
        int l = left;
        int h = mid; // 오류 수정: mid에서 시작해야 함
        int index = 0;
        Comparable[] temp = new Comparable[right - left]; // Comparable로 수정
        
        while (l < mid && h < right) {
            if (arr[l].compareTo(arr[h]) <= 0) { // 비교 방식 수정
                temp[index++] = arr[l++];
            } else {
                temp[index++] = arr[h++];
            }
        }

        while (l < mid) {
            temp[index++] = arr[l++];
        }

        while (h < right) {
            temp[index++] = arr[h++];
        }

        // 배열 복사 방식 수정
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        Integer[] arr = {5, 2, 9, 1, 6, 3};
        MergeSort.sort(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 6, 9]
    }
}

카운팅 소트

import java.util.Arrays;

class CountingSort {
    public static void sort(int[] arr) {
        if (arr.length == 0) return; // 빈 배열 처리

        // 1. 최댓값 찾기
        int max = Arrays.stream(arr).max().orElse(0);

        // 2. 카운트 배열 생성 및 값 채우기
        int[] count = new int[max + 1];
        for (int num : arr) {
            count[num]++;
        }

        // 3. 누적합 계산
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 4. 결과 배열에 정렬된 값 채우기
        int[] sorted = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            sorted[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        // 5. 정렬된 결과를 원본 배열에 복사
        System.arraycopy(sorted, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        CountingSort.sort(arr);
        System.out.println(Arrays.toString(arr)); // [1, 2, 2, 3, 3, 4, 8]
    }
}

카운팅 소트는 중복되는 숫자를 저장할 때 메모리 사용을 최소화하는 정렬이다.

퀵정렬

import java.util.Arrays;

public class QuickSortMiddlePivot {

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;

        int pivotIndex = left + (right - left) / 2;  // 가운데 값을 피벗으로 선택
        int pivot = arr[pivotIndex];
        int pl = left;
        int pr = right;

        while (pl <= pr) {
            // a[pl]은 피벗 이하(≤)인 값을 찾을 때까지 오른쪽으로 이동
            while (arr[pl] <= pivot) pl++;
            // a[pr]은 피벗 이상(≥)인 값을 찾을 때까지 왼쪽으로 이동
            while (arr[pr] >= pivot) pr--;

            if (pl <= pr) {
                swap(arr, pl, pr);
                pl++;
                pr--;
            }
        }

        // 분할 후 재귀적으로 정렬 수행
        quickSort(arr, left, pr);
        quickSort(arr, pl, right);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

• 퀵정렬의 기저 사례는 모든 그룹이 1명씩 남으면 정렬이 완성된다.
• 배열을 두 그룹으로 나누기 위해 배열에서 가운데 값을 피벗으로 선택하고, 왼쪽을 pl, 오른쪽을 pr로 둔다.
• a[pl]은 피벗 이하인 값을 찾아 왼쪽으로 이동한다.
• a[pr]은 피벗 이상인 값을 찾아 오른쪽으로 이동한다.
• 값을 찾으면 pl과 pr이 위치하는 원소의 값을 서로 교환한다.
• pl과 pr이 교차하면 left ~ pr / pl ~ right 두개의 구간으로 나눈다. (피벗도 포함 가능)