1. 삽입 정렬 (Insertion Sort)

삽입 정렬은 현재 위치의 요소를 이미 정렬된 앞부분의 적절한 위치에 찾아 넣는 방식입니다. 구현이 간단하며 데이터가 거의 정렬된 상태에서는 매우 효율적입니다. 시간 복잡도는 평균 $O(n^2)$이며, 안정 정렬(Stable Sort)에 속합니다.

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

2. 쉘 정렬 (Shell Sort)

삽입 정렬의 단점인 '먼 거리 이동'을 보완한 알고리즘입니다. 일정한 간격(Gap)을 두고 그룹을 나누어 각 그룹별로 삽입 정렬을 수행한 뒤, 점진적으로 간격을 줄여가며 최종적으로 전체를 정렬합니다. 삽입 정렬보다 빠르지만 불안정 정렬(Unstable Sort)입니다.

public void shellSort(int[] data) {
    int n = data.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int target = data[i];
            int j = i;
            while (j >= gap && data[j - gap] > target) {
                data[j] = data[j - gap];
                j -= gap;
            }
            data[j] = target;
        }
    }
}

3. 힙 정렬 (Heap Sort)

이진 힙(Binary Heap) 자료구조를 활용하는 정렬 방식입니다. 오름차순 정렬을 위해 최대 힙(Max Heap)을 구성한 후, 루트 노드(최대값)를 마지막 요소와 교체하고 힙 크기를 줄여가며 다시 힙 구조를 유지(Heapify)하는 과정을 반복합니다.

public void heapSort(int[] data) {
    int n = data.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        rebuildHeap(data, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
        swap(data, 0, i);
        rebuildHeap(data, i, 0);
    }
}

private void rebuildHeap(int[] data, int size, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left < size && data[left] > data[largest]) largest = left;
    if (right < size && data[right] > data[largest]) largest = right;

    if (largest != root) {
        swap(data, root, largest);
        rebuildHeap(data, size, largest);
    }
}

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

4. 선택 정렬 (Selection Sort)

전체 배열에서 최소값(혹은 최대값)을 찾아 가장 앞에 위치한 데이터와 교체하는 방식입니다. 로직이 직관적이지만 성능 면에서는 $O(n^2)$으로 낮으며 불안정 정렬에 해당합니다.

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

5. 버블 정렬 (Bubble Sort)

인접한 두 요소를 비교하여 조건에 맞지 않으면 자리를 바꾸는 과정을 반복합니다. 한 회전이 끝날 때마다 가장 큰 요소가 배열의 마지막으로 이동합니다. 교체가 발생하지 않을 경우 조기 종료하는 최적화가 가능합니다.

public void bubbleSort(int[] data) {
    int n = data.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (data[j] > data[j + 1]) {
                swap(data, j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

6. 퀵 정렬 (Quick Sort)

피벗(Pivot)을 설정하고 이를 기준으로 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 분할한 뒤 재귀적으로 정렬하는 분할 정복(Divide and Conquer) 알고리즘입니다. 평균적으로 $O(n \log n)$의 뛰어난 속도를 보여줍니다.

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

private int partition(int[] data, int low, int high) {
    int pivot = data[low];
    int i = low;
    int j = high;
    
    while (i < j) {
        while (i < j && data[j] >= pivot) j--;
        while (i < j && data[i] <= pivot) i++;
        swap(data, i, j);
    }
    swap(data, low, i);
    return i;
}

7. 병합 정렬 (Merge Sort)

배열을 최소 단위까지 쪼갠 뒤, 다시 합치면서 정렬을 수행하는 방식입니다. 항상 $O(n \log n)$의 시간 복잡도를 보장하며 안정 정렬이라는 장점이 있지만, 병합 과정에서 추가적인 메모리 공간이 필요합니다.

public void mergeSort(int[] data, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(data, left, mid);
        mergeSort(data, mid + 1, right);
        merge(data, left, mid, right);
    }
}

private void merge(int[] data, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        temp[k++] = (data[i] <= data[j]) ? data[i++] : data[j++];
    }
    while (i <= mid) temp[k++] = data[i++];
    while (j <= right) temp[k++] = data[j++];

    for (int l = 0; l < temp.length; l++) {
        data[left + l] = temp[l];
    }
}