Как устроена сортировка вставками? Когда она эффективна?

Сортировка вставками строит отсортированную часть массива постепенно. Каждый новый элемент берется из неотсортированной части и вставляется на подходящее место среди уже…

Сортировка вставками строит отсортированную часть массива постепенно. Каждый новый элемент берется из неотсортированной части и вставляется на подходящее место среди уже отсортированных элементов.

Этот принцип похож на сортировку карт в руке: новую карту вставляют туда, где она должна стоять.

Идея алгоритма

Массив делится на две части:

• левая часть уже отсортирована;
• правая часть еще не обработана.

На каждом шаге алгоритм берет первый элемент из правой части и сдвигает элементы левой части вправо, пока не найдет место для вставки.

Пример

Исходный массив:

[5, 2, 4, 1]

Считаем, что [5] уже отсортирована.

Берем 2 и вставляем перед 5:

[2, 5, 4, 1]

Берем 4 и вставляем между 2 и 5:

[2, 4, 5, 1]

Берем 1 и вставляем в начало:

[1, 2, 4, 5]

Код

function insertionSort(values) {
  const result = [...values];

  for (let i = 1; i < result.length; i++) {
    const current = result[i];
    let j = i - 1;

    while (j >= 0 && result[j] > current) {
      result[j + 1] = result[j];
      j--;
    }

    result[j + 1] = current;
  }

  return result;
}

function insertionSort(values: number[]): number[] {
  const result = [...values];

  for (let i = 1; i < result.length; i++) {
    const current = result[i];
    let j = i - 1;

    while (j >= 0 && result[j] > current) {
      result[j + 1] = result[j];
      j--;
    }

    result[j + 1] = current;
  }

  return result;
}

func insertionSort(values []int) []int {
  result := append([]int(nil), values...)

  for i := 1; i < len(result); i++ {
    current := result[i]
    j := i - 1

    for j >= 0 && result[j] > current {
      result[j+1] = result[j]
      j--
    }

    result[j+1] = current
  }

  return result
}

public class Example {
  static int[] insertionSort(int[] values) {
    int[] result = java.util.Arrays.copyOf(values, values.length);

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

      while (j >= 0 && result[j] > current) {
        result[j + 1] = result[j];
        j--;
      }

      result[j + 1] = current;
    }

    return result;
  }
}

def insertion_sort(values):
  result = values.copy()

  for i in range(1, len(result)):
    current = result[i]
    j = i - 1

    while j >= 0 and result[j] > current:
      result[j + 1] = result[j]
      j -= 1

    result[j + 1] = current

  return result

Сложность

Сложность зависит от исходного порядка массива.

• худший случай: O(n²), если массив отсортирован в обратном порядке;
• средний случай: O(n²);
• лучший случай: O(n), если массив уже отсортирован;
• дополнительная память: O(1), если сортировать на месте.

Когда сортировка вставками эффективна

Почти отсортированные данные

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

Маленькие массивы

На небольших массивах простые алгоритмы часто выигрывают за счет низких накладных расходов.

Онлайн-обработка

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

Часть гибридных алгоритмов

В практических реализациях сложных сортировок сортировка вставками иногда используется для маленьких подмассивов.

Особенности

Преимущества:

• простая реализация;
• хороша для почти отсортированных данных;
• устойчива при классической реализации;
• не требует дополнительной памяти.

Недостатки:

• медленная на больших случайных массивах;
• в худшем случае выполняет много сдвигов.

Вывод

сортировка вставками вставляет каждый новый элемент в уже отсортированную часть массива. Она особенно эффективна для маленьких и почти отсортированных наборов данных.