Colin's Blog
[java] 자바 정렬 알고리즘의 시간 복잡도

자료를 정렬하는 것은 프로그래밍에서 매우 일반적이고 중요한 작업입니다. 자바 언어에서는 다양한 정렬 알고리즘을 지원합니다. 각 정렬 알고리즘은 입력 데이터의 크기에 따라 수행 시간이 달라집니다. 이 글에서는 자바에서 사용되는 일반적인 정렬 알고리즘들의 시간 복잡도를 살펴보겠습니다.

선택 정렬 (Selection Sort)

선택 정렬은 가장 작은(또는 큰) 원소를 선택해서 맨 앞(또는 맨 뒤)의 원소와 교환하는 방식으로 정렬을 수행합니다. 선택 정렬의 시간 복잡도는 O(n^2) 입니다.

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

삽입 정렬 (Insertion Sort)

삽입 정렬은 배열을 순차적으로 탐색하면서 각 원소를 이미 정렬된 배열 부분에 삽입하는 방식으로 정렬을 수행합니다. 삽입 정렬의 시간 복잡도는 O(n^2) 입니다.

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

퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복 알고리즘을 이용하여 배열을 정렬합니다. 평균적으로 가장 빠른 정렬 알고리즘 중 하나이며, 시간 복잡도는 O(n log n) 입니다.

public class QuickSort {
    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;
    }
}

결론

자바에서 제공하는 정렬 알고리즘들은 각각 다른 시간 복잡도를 가지고 있으며, 입력 데이터의 크기에 따라 성능이 달라집니다. 적절한 상황에 맞는 정렬 알고리즘을 선택하여 프로그래밍을 하도록 합니다.

위의 코드는 각 정렬 알고리즘의 예시이며, 실제 사용 시 상황에 맞게 수정해야 합니다.

참고 문헌:

© 2018 Colin. All rights reserved.