이진 삽입 정렬

왜 우리는 정렬합니까?

종종 우리가 어레이에서 수행하는 작업, 예를 들어 검색은 배열이 정렬될 때 크게 최적화될 수 있습니다.

이유? 관련 데이터를 훨씬 더 빨리 찾을 수 있기 때문입니다.

고전적인 삽입 정렬은 다음과 같습니다.

public static void insertionSort(int[] nums) {

    for(int i=1; i < nums.length; ++i) {
        int current = nums[i], j;

        for(j=i-1; j >= 0 && current < nums[j]; --j)
            nums[j+1] = nums[j];

        nums[j+1] = current;
    }
}

배열의 왼쪽에 정렬된 창을 만들고 창의 내부(오른쪽) 가장자리에서 선형으로 횡단하여 올바른 위치에 각각의 새 요소를 추가합니다.

배열이 역순으로 정렬되면 모든 요소를 ​​다른 모든 요소와 비교해야 하므로 O(n^2)의 최악의 경우 시간 복잡도를 관찰합니다.

더 잘할 수 있을까요? 해보자!

이진 삽입 정렬

고전적인 삽입 정렬을 분석하면 다음 두 가지 핵심 단계를 중심으로 합니다.

정렬된 창에서 다음 요소의 적절한 삽입 위치 찾기 - O(n)

더 큰 요소를 모두 이동하여 공간 확보 - O(n)

이 두 단계 모두 선형 시간이 걸리며 모든 요소에 적용됩니다(O(n)).

Classic Time Complexity = O(n (n + n)) = O(n^2 + n^2) = O(n^2)

개별 단계를 최적화해 보겠습니다.

Step 1. Is there anyway we can find the insert position faster than O(n)?

사실 그렇습니다! 창이 정렬되어 있으므로 선형 검색 대신 이진 검색을 사용하여 이 단계를 기하급수적으로 개선할 수 있습니다.

Step 2. Is shifting elements one by one the only way?

안타깝게도 Java에는 프로세스를 최적화하는 내장 시스템 APISystem.arraycopy()가 있습니다.

Binary 변형에 대한 Java 구현을 살펴보겠습니다.

public static void insertionSortCoffeeless(int[] arr) {
    for(int i=1; i < arr.length; ++i) {
        current = arr[i];

        int j = findInsertPosition(arr, 0, i-1, current);
        System.arraycopy(arr, j, arr, j + 1, i - j);

        arr[j] = current;
    }
}

private static int findInsertPosition(int[] nums, int lB, int rB, int target) {
    int mid=(lB+rB)/2;

    while(lB<=rB) {
        mid=(lB+rB)/2;

        if(target < nums[mid]) rB=mid-1;
        else lB = mid+1;
    }

    return target < nums[mid] ? mid : mid+1;
}

Binary Time Complexity = O(n (log n + n)) = O(nlog n + n^2) = O(n^2)

개선 후에도 우리는 여전히 n-제곱의 Big O를 가지고 있지만 파생에 따라 다소 더 빠르게 수행되어야 합니다.

병목 현상은 올바른 위치를 찾는 것에서 모든 더 큰 요소를 하나씩 이동하는 것으로 이동합니다.

실제로 얼마나 빠릅니까?

다음은 증가하는 크기의 32비트 정수 배열에서 일반적인 정렬을 비교한 결과입니다.



이진 변형은 최대 20,000개 요소 목록에 대해 실용적입니다(5ms 미만).

그리고 미래에 컴퓨터 아키텍처가 가변 길이 메모리 블록을 일정한 시간에 덮어쓸 수 있도록 허용한다면 O(nlog n)의 시간 복잡도를 보장하는 안정적인 제자리 정렬이 가능합니다.

다음 시간까지,
료

참조

System.arraycopy() | Java 17 Docs

Insertion Sort Variants | Wikipedia