1. 직접 삽입 정렬 (Direct Insertion Sort)

이미 정렬된 배열에 새 데이터를 삽입하는 방식으로 작동합니다. 첫 번째 두 수를 정렬한 후 순차적으로 추가하여 전체 배열을 정렬합니다.

핵심 아이디어: 이미 정렬된 n-1개의 요소에 대해 새로운 요소를 삽입하여 전체 배열을 정렬합니다.

코드 구현:

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

2. 셸 정렬 (Shell Sort)

삽입 정렬의 효율성을 개선한 알고리즘으로, 간격을 줄여가며 정렬을 수행합니다.

코드 구현:

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

3. 단순 선택 정렬 (Simple Selection Sort)

배열에서 최소 값을 찾아서 앞으로 이동시키는 방식입니다.

코드 구현:

public void selectSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        int minIndex = i;
        for (int j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

4. 힙 정렬 (Heap Sort)

대규모 데이터 처리에 효과적인 알고리즘으로, 최대 힙 구조를 활용합니다.

코드 구현:

public void heapSort(int[] arr) {
    int len = arr.length;
    for (int i = len / 2 - 1; i >= 0; i--) {
        heapify(arr, len, i);
    }
    for (int i = len - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

private void heapify(int[] arr, int size, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    
    if (left < size && arr[left] > arr[largest]) {
        largest = left;
    }
    
    if (right < size && arr[right] > arr[largest]) {
        largest = right;
    }
    
    if (largest != root) {
        int swap = arr[root];
        arr[root] = arr[largest];
        arr[largest] = swap;
        heapify(arr, size, largest);
    }
}

5. 버블 정렬 (Bubble Sort)

연속적으로 인접 요소를 비교하여 큰 값을 끝으로 이동시키는 방식입니다.

코드 구현:

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

6. 퀵 정렬 (Quick Sort)

분할 정복 전략을 사용하는 알고리즘으로, 기준값을 중심으로 분할합니다.

코드 구현:

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    
    int pivot = arr[right];
    int i = left - 1;
    
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, right);
    
    quickSort(arr, left, i);
    quickSort(arr, i + 2, right);
}

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

7. 병합 정렬 (Merge Sort)

분할 정복 전략을 사용하며, 두 부분을 병합하여 정렬합니다.

코드 구현:

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

private void merge(int[] arr, 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) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    System.arraycopy(temp, 0, arr, left, temp.length);
}

8. 기수 정렬 (Radix Sort)

각 자리수를 기준으로 정렬하는 방식으로, 정수 데이터에 적합합니다.

코드 구현:

public void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    
    for (int exp = 1; max / exp > 0; exp *= 10) {
        @SuppressWarnings("unchecked")
        List<Integer>[] buckets = new ArrayList[10];
        
        for (int i = 0; i < 10; i++) {
            buckets[i] = new ArrayList<>();
        }
        
        for (int num : arr) {
            int index = (num / exp) % 10;
            buckets[index].add(num);
        }
        
        int k = 0;
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                arr[k++] = num;
            }
        }
    }
}

9. 계수 정렬 (Counting Sort)

데이터 범위가 제한된 경우에 효과적인 알고리즘입니다.

코드 구현:

public static int[] countingSort(int[] arr) {
    if (arr.length == 0) return arr;
    
    int min = Arrays.stream(arr).min().getAsInt();
    int max = Arrays.stream(arr).max().getAsInt();
    
    int[] count = new int[max - min + 1];
    for (int num : arr) {
        count[num - min]++;
    }
    
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i]-- > 0) {
            arr[index++] = i + min;
        }
    }
    return arr;
}

10. 바구니 정렬 (Bucket Sort)

데이터 분포를 고려한 정렬 알고리즘으로, 공간 대신 시간을 효율적으로 사용합니다.

코드 구현:

public static void bucketSort(double[] arr, int bucketSize) {
    double min = Arrays.stream(arr).min().getAsDouble();
    double max = Arrays.stream(arr).max().getAsDouble();
    
    int bucketCount = (int) ((max - min) / bucketSize) + 1;
    List buckets = new ArrayList<>();
    
    for (int i = 0; i < bucketCount; i++) {
        buckets.add(new ArrayList<>());
    }
    
    for (double num : arr) {
        int index = (int) ((num - min) / bucketSize);
        buckets.get(index).add(num);
    }
    
    for (List<Double> bucket : buckets) {
        Collections.sort(bucket);
    }
    
    int index = 0;
    for (List<Double> bucket : buckets) {
        for (double num : bucket) {
            arr[index++] = num;
        }
    }
}

11. 알고리즘 비교

• 시간 복잡도:
  • 제곱 시간: 삽입 정렬, 선택 정렬, 버블 정렬
  • 선형 로그 시간: 퀵 정렬, 힙 정렬, 병합 정렬
  • O(n^1+ε): 셸 정렬
  • 선형 시간: 기수 정렬, 바구니 정렬
• 안정성:
  • 안정적: 버블 정렬, 삽입 정렬, 병합 정렬, 기수 정렬
  • 비안정적: 선택 정렬, 퀵 정렬, 셸 정렬, 힙 정렬