01. Sorting

1. Bubble Sort

• 인접한 두 수를 비교하며 정렬
• 시간복잡도 (최악, 평균, 최선) : $O(n^2)$, $O(n^2)$, $O(n)$
• 안정성 o

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. Selection Sort

• 배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환
• 시간복잡도 (최악, 평균, 최선) : $O(n^2)$, $O(n^2)$, $O(n^2)$

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

3. Insertion Sort

• 정렬된 부분 배열에 현재 원소를 삽입
• 시간복잡도 (최악, 평균, 최선) : $O(n^2)$, $O(n^2)$, $O(n)$
• 안정성 o

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

4. Quick Sort

• 피벗을 기준으로 배열을 분할하고 각 부분 배열을 재귀적으로 정렬
• 시간복잡도 (최악, 평균, 최선) : $O(n^2)$, $O(n \log n)$, $O(n \log n)$

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

5. Merge Sort

• 배열을 반으로 나누고 각각을 정렬한 후 병합
• 시간복잡도 (최악, 평균, 최선) : $O(n \log n)$, $O(n \log n)$, $O(n \log n)$
• 안정성 o

public static void mergeSort(int[] arr) {
    if (arr.length > 1) {
        int mid = arr.length / 2;

        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }
}

private static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

6. Heap Sort

• 배열을 최소힙으로 변환한 후 힙에서 최소값을 하나씩 제거하여 정렬
• 시간복잡도 (최악, 평균, 최선) : $O(n \log n)$, $O(n \log n)$, $O(n \log n)$

import java.util.PriorityQueue;

public class HeapSort {
    public static void heapSort(int[] array) {
        // 최소 힙 생성
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 배열의 모든 요소를 힙에 추가
        for (int value : array) {
            minHeap.add(value);
        }

        // 힙에서 요소를 하나씩 꺼내어 다시 배열에 저장
        for (int i = 0; i < array.length; i++) {
            array[i] = minHeap.poll();
        }
    }

    // 배열을 출력하는 메소드
    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {10, 3, 5, 1, 15, 6, 9};
        System.out.println("Original array:");
        printArray(array);

        heapSort(array);
        System.out.println("Sorted array:");
        printArray(array);
    }
}

7. Shell Sort

• 간격을 두고 배열을 부분 정렬하고 점차 간격을 줄여나감
• 시간복잡도 (최악, 평균, 최선) : $O(n^2)$, $O(n \log n)$ ~ $O(n^{3/2})$, $O(n \log n)$

public static void shellSort(int[] arr) {
    int n = arr.length;

    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

연습문제

10818번 - 최소, 최대 (힙정렬로 해결)

10818번 - 최소, 최대 (합병정렬로 해결)