«1. Обзор

В этом уроке мы обсудим алгоритм сортировки вставками и рассмотрим его реализацию на Java.

Сортировка вставками — эффективный алгоритм для упорядочения небольшого количества элементов. Этот метод основан на том, как карточные игроки сортируют карты.

Мы начинаем с пустой левой рукой и картами, выложенными на стол. Затем мы убираем одну карту со стола и вставляем ее в правильное положение в левой руке. Чтобы найти правильную позицию для новой карты, мы сравниваем ее с уже отсортированным набором карт в руке, справа налево.

Давайте начнем с понимания шагов алгоритма в форме псевдокода.

2. Псевдокод

Мы собираемся представить наш псевдокод для сортировки вставками в виде процедуры INSERTION-SORT, принимающей в качестве параметра массив A[1 .. n] из n элементов для сортировки. Алгоритм сортирует входной массив на месте (путем перестановки элементов в массиве A).

После завершения процедуры входной массив A содержит перестановку входной последовательности, но в отсортированном порядке: 

INSERTION-SORT(A)

for i=2 to A.length
    key = A[i]
    j = i - 1 
    while j > 0 and A[j] > key
        A[j+1] = A[j]
        j = j - 1
    A[j + 1] = key

Давайте кратко рассмотрим приведенный выше алгоритм.

Индекс i указывает позицию текущего элемента в массиве для обработки.

Начнем со второго элемента, так как по определению массив с одним элементом считается отсортированным. Элемент с индексом i называется ключом. Получив ключ, вторая часть алгоритма занимается поиском его правильного индекса. Если ключ меньше, чем значение элемента с индексом j, то ключ перемещается на одну позицию влево. Процесс продолжается до тех пор, пока не будет достигнут элемент, меньший ключа.

Важно отметить, что до начала итерации по нахождению правильного положения ключа с индексом i массив A[1 .. j – 1] уже отсортирован.

3. Императивная реализация

Для императивного случая мы собираемся написать функцию с именем insertionSortImperative, принимая в качестве параметра массив целых чисел. Функция начинает перебирать массив со второго элемента.

В любой момент во время итерации мы могли бы думать об этом массиве как о логически разделенном на две части; левая сторона является отсортированной, а правая содержит еще не отсортированные элементы.

Здесь важно отметить, что после нахождения правильной позиции, в которой мы будем вставлять новый элемент, мы сдвигаем (а не меняем местами) элементы вправо, чтобы освободить место для него. 

public static void insertionSortImperative(int[] input) {
    for (int i = 1; i < input.length; i++) { 
        int key = input[i]; 
        int j = i - 1;
        while (j >= 0 && input[j] > key) {
            input[j + 1] = input[j];
            j = j - 1;
        }
        input[j + 1] = key; 
    }
}

Далее давайте создадим тест для метода выше: 

@Test
public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() {
    int[] input = {6, 2, 3, 4, 5, 1};
    InsertionSort.insertionSortImperative(input);
    int[] expected = {1, 2, 3, 4, 5, 6};
    assertArrayEquals("the two arrays are not equal", expected, input);
}

Тест выше доказывает, что алгоритм правильно сортирует в порядке возрастания входной массив \u003c6, 2, 3, 4, 5, 1 \u003e.

4. Рекурсивная реализация

Функция для рекурсивного случая называется insertionSortRecursive и принимает на вход массив целых чисел (такой же, как и для императивного случая).

Отличие здесь от императивного случая (несмотря на то, что он рекурсивный) заключается в том, что он вызывает перегруженную функцию со вторым аргументом, равным количеству элементов для сортировки.

Поскольку мы хотим отсортировать весь массив, мы передадим количество элементов, равное его длине: 

public static void insertionSortRecursive(int[] input) {
    insertionSortRecursive(input, input.length);
}

Рекурсивный случай немного сложнее. Базовый случай возникает, когда мы пытаемся отсортировать массив с одним элементом. В этом случае мы ничего не делаем.

Все последующие рекурсивные вызовы сортируют предопределенную часть входного массива — начиная со второго элемента и до конца массива: 

private static void insertionSortRecursive(int[] input, int i) {
    if (i <= 1) {
        return;
    }
    insertionSortRecursive(input, i - 1);
    int key = input[i - 1];
    int j = i - 2;
    while (j >= 0 && input[j] > key) {
        input[j + 1] = input[j];
        j = j - 1;
    }
    input[j + 1] = key;
}

А вот как выглядит стек вызовов для входной массив из 6 элементов: 

insertionSortRecursive(input, 6)
insertionSortRecursive(input, 5) and insert the 6th item into the sorted array
insertionSortRecursive(input, 4) and insert the 5th item into the sorted array
insertionSortRecursive(input, 3) and insert the 4th item into the sorted array
insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array
insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array

Давайте также посмотрим тест для него: 

@Test
public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() {
    int[] input = {6, 4, 5, 2, 3, 1};
    InsertionSort.insertionSortRecursive(input);
    int[] expected = {1, 2, 3, 4, 5, 6};
    assertArrayEquals("the two arrays are not equal", expected, input);
}

Тест выше доказывает, что алгоритм правильно сортирует в порядке возрастания входной массив \u003c6, 2, 3, 4, 5, 1\u003e.

5. Сложность времени и пространства

Время выполнения процедуры INSERTION-SORT составляет O(n^2). Для каждого нового элемента мы перебираем справа налево уже отсортированную часть массива, чтобы найти его правильное положение. Затем мы вставляем его, сдвигая элементы на одну позицию вправо.

«Алгоритм сортируется на месте, поэтому его пространственная сложность составляет O(1) для императивной реализации и O(n) для рекурсивной реализации.

6. Заключение

В этом уроке мы увидели, как реализовать сортировку вставками.

Этот алгоритм полезен для сортировки небольшого количества элементов. Это становится неэффективным при сортировке входных последовательностей, содержащих более 100 элементов.

Имейте в виду, что, несмотря на свою квадратичную сложность, он сортирует на месте без необходимости дополнительного пространства, как в случае сортировки слиянием.

Весь код можно найти на GitHub.