[java] 자바 정렬 알고리즘의 장단점

15 Dec 2023

java

자바에서는 다양한 정렬 알고리즘이 제공됩니다. 이러한 알고리즘들은 각각 장단점이 있어 다른 상황에 맞게 선택할 수 있습니다. 이 포스트에서는 몇 가지 자바 정렬 알고리즘의 장단점을 살펴보겠습니다.

1. 버블 정렬 (Bubble Sort)

장점
- 구현이 간단하고 이해하기 쉽습니다.
- 정렬하려는 데이터가 이미 거의 정렬된 경우에는 효율적일 수 있습니다.
단점
- 시간 복잡도가 좋지 않아 대규모 데이터에는 적합하지 않습니다.

// Java 코드로 구현한 버블 정렬
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-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

2. 퀵 정렬 (Quick Sort)

장점
- 빠른 정렬 알고리즘 중 하나로 평균적으로 높은 성능을 보입니다.
단점
- 최악의 경우에는 성능이 급격히 저하될 수 있습니다.

// Java 코드로 구현한 퀵 정렬
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++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // Swap arr[i+1] and arr[high]
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;
        return i+1;
    }
}

3. 병합 정렬 (Merge Sort)

장점
- 안정적인 정렬 알고리즘으로 항상 일정한 성능을 보장합니다.
- 대규모 데이터에 대해 효율적으로 동작합니다.
단점
- 추가적인 메모리 공간이 필요하다는 점입니다.

// Java 코드로 구현한 병합 정렬
public class MergeSort {
    public static void mergeSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid+1, high);
            merge(arr, low, mid, high);
        }
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        int n1 = mid - low + 1;
        int n2 = high - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) {
            L[i] = arr[low + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }
        // 병합 로직은 생략
    }
}

이제 여러 자바 정렬 알고리즘의 장단점을 알아보았습니다. 주어진 상황과 데이터에 맞게 적절한 알고리즘을 선택하면 됩니다.