[알고리즘] 자바 정렬 알고리즘 정리 및 인터페이스와 함수

정렬 알고리즘이란?

정렬 알고리즘이란, 목록 안에 저장된 원소들을 일정한 순서대로 정렬[재배치]하는 알고리즘입니다.

사용하는 이유 ❓
좀 더 효율적인 알고리즘 및 배열 및 리스트를 정리하기 위해서 사용합니다.
정렬 알고리즘은 시간 복잡도와 메모리 사용량에 따라서 상황에 맞는 알고리즘을 사용하면 됩니다.

• 정렬 시 고려사항
  • 정렬할 대상 데이터의 양 또는 메모리
  • 필요한 추가 메모리의 양

버블 정렬(Bubble Sort)

버블 정렬은 거품이 수면으로 올라오는 것처럼 정렬을 하기 때문에 버블 정렬이라고 명칭합니다.

인접한 두 요소를 비교하여 필요시 오름차순 또는 내림차순을 기준으로 교환하는 과정을 반복합니다.

보통 버블 정렬은 구현이 간단하지만 비효율적이므로, 교육용으로 알고리즘의 기본 개념을 설명하거나 작은 데이터셋에 사용하고 있습니다.

• 장점
  • 구현이 매우 간단하다.
  • 데이터가 거의 정렬된 상태에서는 효율적이다.
• 단점
  • 시간 복잡도가 O(n²)로 매우 비효율적이다.

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

선택 정렬(Selection Sort)

선택 정렬은 매 단계마다 최솟값(또는 최댓값)을 찾아 해당 위치로 이동시키는 방식으로 동작합니다. 보통 선택 정렬은 구현이 간단하지만 비효율적이므로, 주로 작은 배열이나 정렬을 이해하기 위한 학습 목적으로 사용됩니다.

• 장점
  • 구현이 매우 간단하다.
  • 데이터 이동 횟수가 적다.
• 단점
  • 시간 복잡도가 O(n²)로 매우 비효율적이다.

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

삽입 정렬(Insertion Sort)

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분에 삽입하는 방식입니다. 데이터셋이 이미 정렬된 상태에서는 효율적이며, 작은 데이터셋에서는 상대적으로 성능이 좋을 수 있습니다.

• 장점
  • 구현이 매우 간단하다.
  • 데이터가 거의 정렬된 상태에서는 효율적이다.
  • 제자리 정렬이다.
• 단점
  • 시간 복잡도가 O(n²)로 매우 비효율적이다.

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

셀 정렬(Shell Sort)

셀 정렬은 삽입 정렬의 일반화된 형태로, 일정한 간격으로 떨어진 요소들을 삽입 정렬하여 정렬하는 방식입니다. 간격을 점차 줄여가며 마지막 단계에서는 일반 삽입 정렬을 수행합니다.

• 장점
  • 삽입 정렬보다 일반적으로 빠르다.
  • 간격에 따라서 효율성이 크게 달라진다.
• 단점
  • 최적의 성능을 보장하지 않는다.

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

병합 정렬(Merge Sort)

병합 정렬은 분할 정복(divide and conquer) 방법을 사용해서 배열을 반으로 나뉘어 각각 정렬한 후, 정렬된 부분을 병합하는 방식으로 작동합니다. 안정적이고 일정한 성능을 보장하지만, 추가적인 메모리 공간이 필요하다는 단점이 있습니다.

• 장점
  • 시간 복잡도가 O(n log n)으로 안정적이다.
  • 안정 정렬이다.
• 단점
  • 추가적인 메모리 공간이 필요하다.

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

void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; ++i) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; ++j) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    }
    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++]; 
    }
}

힙 정렬(Heap Sort)

힙 정렬은 최대 힙이나 최소 힙 자료구조를 이용해서 배열을 정렬하는 방식입니다. 힙 정렬은 항상 O(n log n)의 시간 복잡도를 가지며, 추가 메모리 공간이 거의 필요하지 않습니다.

• 장점
  • 시간 복잡도가 O(n log n)으로 안정적이다.
  • 추가적인 메모리 공간이 거의 필요 없다.
• 단점
  • 불안정 정렬이다.

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

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

퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복 (divide and conquer) 방법을 사용해서 배열을 정렬하는 방식입니다. 피벗(pivot)을 기준으로 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할하며 정렬합니다. 평균적으로 빠른 속도를 보이지만 최악의 경우에는 성능이 떨어질 수 있습니다.

• 장점
  • 평균적으로 매우 빠르다.
  • 제자리 정렬이다.
• 단점
  • 최악의 경우 시간 복잡도가 O(n²)이다.
  • 불안정 정렬이다.

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

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

---

이와 같은 다양한 정렬 알고리즘을 상황에 맞게 선택해서 사용하면 됩니다. 데이터의 크기와 특성에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.

자바에 제공하는 정렬 인터페이스 및 함수

Arrays.sort()

Arrays.sort()는 Arrays 클래스에서 제공하는 배열을 정렬하는 메서드입니다. 내부적으로 빠른 정렬을 위해 두 개의 피벗을 사용하는 Dual-Pivot Quicksort 알고리즘을 사용합니다. 평균적으로 O(n log n)의 시간 복잡도를 가집니다.

int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
Arrays.sort(arr);

Collection.sort()

Collection.sort()는 Collection 클래스에서 제공하는 컬렉션을 정렬하는 메서드입니다. 합병 정렬과 삽입 정렬의 하이브리드 알고리즘으로 Timsort 알고리즘을 사용합니다. 대부분의 실전 데이터에 대해 매우 효율적이지만, 최악의 경우에는 O(n log n)의 시간 복잡도를 가집니다.

List<Integer> list = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);
Collections.sort(list);

Stream.sorted()

Stream.sorted()는 Java 8부터 도입된 Stream을 정렬하는 스트림 API의 메서드입니다. 내부적으로 컬렉션 정렬과 마찬가지로, 합병 정렬과 하이브리드 알고리즘으로 Timsort 알고리즘을 사용합니다. 대부분의 실전 데이터에 대해 매우 효율적이지만, 최악의 경우에는 O(n log n)의 시간 복잡도를 가집니다.

List<Integer> list = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);
List<Integer> sortedList = list.stream().sorted().collect(Collectors.toList());

PriorityQueue

PriorityQueue 클래스는 힙 정렬을 기반으로 하는 우선순위 큐를 제공합니다. 요소를 추가하고 제거하는 동안 내부적으로 힙을 유지합니다. 항상 O(log n)의 시간 복잡도를 가지며, 요소를 추가하거나 제거할 때 힙을 재구성합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(1);
pq.add(4);

TreeSet

TreeSet 클래스는 이진 검색 트리를 기반으로 요소를 정렬하여 저장합니다. 내부적으로 Red-Black Tree를 사용하며 요소를 추가하거나 제거할 때 트리를 재구성합니다. 항상 O(log n)의 시간복잡도를 가집니다. 

TreeSet<Integer> treeSet = new TreeSet<>(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5));