[java] 정렬 알고리즘의 시간 복잡도

14 Dec 2023

java

정렬 알고리즘은 데이터를 특정한 기준에 따라 순서대로 나열하는 알고리즘입니다. 자바에서는 배열이나 컬렉션을 정렬할 때 여러 가지 알고리즘이 활용됩니다. 각 정렬 알고리즘은 시간 복잡도가 다르기 때문에 어떤 상황에서 어떤 알고리즘을 사용하는지 이해하는 것이 중요합니다.

버블 정렬 (Bubble Sort)

가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 필요에 따라 교환하는 방식으로 동작합니다. 시간 복잡도는 O(n^2)입니다.

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

퀵 정렬 (Quick Sort)

분할 정복 방법을 사용하는 정렬 알고리즘으로, 평균적으로 매우 빠른 수행 속도를 가집니다. 시간 복잡도는 O(n log n) 입니다.

public class QuickSort {
    public void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            sort(arr, low, pi-1);
            sort(arr, pi+1, high);
        }
    }

    private 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;
    }
}

병합 정렬 (Merge Sort)

분할 정복 알고리즘으로, 리스트를 절반으로 잘라 각각을 정렬한 후 병합하는 방식으로 동작합니다. 시간 복잡도는 O(n log n) 입니다.

public class MergeSort {
    public void sort(int[] arr, int l, int r) {
        if (l < r) {
            int m = (l+r) / 2;

            sort(arr, l, m);
            sort(arr, m+1, r);

            merge(arr, l, m, r);
        }
    }

    private void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; ++i) {
            L[i] = arr[l + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[m + 1 + j];
        }

        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

결론

각 정렬 알고리즘은 시간 복잡도와 성능 면에서 차이가 있으며, 데이터의 크기와 정렬 상태에 따라 적절한 알고리즘을 선택해야 합니다. 퀵 정렬과 병합 정렬은 O(n log n) 으로, 대부분의 상황에서 효율적으로 동작합니다. 반면 버블 정렬은 O(n^2) 로 성능이 좋지 않기 때문에 큰 데이터셋에는 적합하지 않을 수 있습니다.

참고 문헌: GeeksforGeeks, Wikipedia