Java에서 O(n^2)과 O(n log n) 알고리즘 정리

 

알고리즘의 시간 복잡도는 코드 실행 속도를 예측하는 중요한 척도입니다. 이번 포스팅에서는 대표적인 O(n^2) 알고리즘과 O(n log n) 알고리즘을 코드 예제와 함께 정리하겠습니다.

O(n^2) 알고리즘

O(n^2) 알고리즘은 입력 크기가 증가할수록 수행 시간이 제곱에 비례하여 증가하는 알고리즘입니다. 대표적으로 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 브루트 포스(Brute Force) 알고리즘 등이 있습니다.

1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 원소를 비교하여 정렬하는 방식으로, 최악의 경우 O(n^2)의 시간 복잡도를 가집니다.

public class BubbleSort {
    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)

선택 정렬은 배열에서 가장 작은 값을 선택해 정렬하는 방식입니다.

public class SelectionSort {
    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)

삽입 정렬은 각 요소를 적절한 위치에 삽입하는 방식으로 정렬합니다.

public class InsertionSort {
    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--;
            }
            arr[j + 1] = key;
        }
    }
}

O(n log n) 알고리즘

O(n log n) 알고리즘은 입력 크기가 증가할 때 비교적 효율적으로 실행됩니다. 대표적인 예로 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)이 있습니다.

1. 퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복(Divide and Conquer) 방식으로 동작하며, 평균적으로 O(n log n)의 시간 복잡도를 가집니다.

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);
            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
    }
}

2. 병합 정렬 (Merge Sort)

병합 정렬은 데이터를 반으로 나누고, 각각 정렬한 후 병합하는 방식으로 동작합니다.

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

3. 힙 정렬 (Heap Sort)

힙 정렬은 힙 트리를 이용한 정렬 알고리즘으로, O(n log n)의 성능을 가집니다.

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

기타 정렬 알고리즘

1. 계수 정렬 (Counting Sort)

계수 정렬은 특정 범위 내의 정수 데이터를 매우 빠르게 정렬하는 알고리즘입니다.

public class CountingSort {
    public static void countingSort(int[] arr, int maxVal) {
        int[] count = new int[maxVal + 1];
        for (int num : arr) {
            count[num]++;
        }
        int index = 0;
        for (int i = 0; i <= maxVal; i++) {
            while (count[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }
}

2. 기수 정렬 (Radix Sort)

기수 정렬은 숫자의 자릿수를 기준으로 여러 번 정렬하는 방식입니다.

public class RadixSort {
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }
}

3. 버킷 정렬 (Bucket Sort)

버킷 정렬은 데이터를 여러 개의 버킷에 나누고 개별적으로 정렬하는 방식입니다.

public class BucketSort {
    public static void bucketSort(float[] arr) {
        List<Float>[] buckets = new List[arr.length];
        for (int i = 0; i < arr.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        for (float num : arr) {
            buckets[(int) (num * arr.length)].add(num);
        }
        for (List<Float> bucket : buckets) {
            Collections.sort(bucket);
        }
    }
}

 

각 정렬 알고리즘은 특정 상황에서 최적의 성능을 발휘할 수 있으므로, 데이터의 특성에 맞는 알고리즘을 선택하는 것이 중요합니다.