삽입 정렬

$k$번째 단계에서 길이 $k$인 접두사가 이미 정렬되어 있다고 합시다. 이 정렬된 접두사를 늘리기 위해, 그 바로 다음 원소를 가져와 해당 원소가 왼쪽 이웃보다 커질 때까지 왼쪽 이웃과 교환할 수 있습니다. 그렇게 되면 이 원소는 왼쪽의 모든 원소보다 크고 오른쪽에 있는 접두사의 모든 원소보다 작다는 뜻이 되며, 따라서 이 원소를 배열의 정렬된 부분에 올바르게 삽입한 것입니다.

void insertion_sort(int *a, int n) {
    for (int k = 1; k < n; k++)
        for (int i = k; i > 0 && a[i - 1] < a[i]; i--)
            // мы ещё не дошли до начала массива и предыдущий элемент меньше
            swap(a[i], a[i - 1]);
}

최악의 경우 실행 시간 역시 이차입니다. 예를 들어 배열이 내림차순으로 정렬되어 있는 경우가 그렇습니다.

하지만 앞의 두 이차 시간 정렬과 달리, 내부 루프에 조기 종료 조건을 추가했기 때문에 일부 좋은 경우에는 실행 시간이 더 짧을 수 있습니다. 예를 들어, 배열이 처음부터 정렬되어 있다면 알고리즘은 $O(n)$번의 연산을 수행합니다.

연습 문제. 배열이 각 원소가 정렬된 배열에서의 위치로부터 최대 $k$만큼 떨어져 있다는 의미에서 “거의 정렬되어” 있다면, 알고리즘이 $O(n k)$번의 연산을 수행함을 보이십시오.