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);
}
Приведенный выше тест доказывает, что алгоритм правильно сортирует в порядке возрастания входной массив <6, 2, 3, 4, 5, 1> .
4. Рекурсивная реализация
Функция для рекурсивного случая называется insertionSortR ecusive и принимает на вход массив целых чисел (такой же, как и для императивного случая).
Отличие здесь от императивного случая (несмотря на то, что он рекурсивный) в том, что он вызывает перегруженную функцию со вторым аргументом, равным количеству элементов для сортировки.
Поскольку мы хотим отсортировать весь массив, мы передадим количество элементов, равное его длине:
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);
}
Приведенный выше тест доказывает, что алгоритм правильно сортирует в порядке возрастания входной массив <6, 2, 3, 4, 5, 1> .
5. Сложность времени и пространства
Время выполнения процедуры INSERTION-SORT составляет O(n^2) . Для каждого нового элемента мы перебираем справа налево уже отсортированную часть массива, чтобы найти его правильное положение. Затем мы вставляем его, сдвигая элементы на одну позицию вправо.
Алгоритм сортируется на месте, поэтому его пространственная сложность составляет O(1) для императивной реализации и O(n) для рекурсивной реализации.
6. Заключение
В этом уроке мы увидели, как реализовать сортировку вставками.
Этот алгоритм полезен для сортировки небольшого количества элементов. Это становится неэффективным при сортировке входных последовательностей, содержащих более 100 элементов.
Имейте в виду, что, несмотря на свою квадратичную сложность, он сортирует на месте без необходимости дополнительного пространства, как в случае сортировки слиянием .
Весь код можно найти на GitHub .