Сортировка вставкой/Insertion sort

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

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

  1. Простой в использовании
  2. Эфективный на малых входных даных
  3. Адаптивный: если входные даные уже частично отсортированы, тогда сортировка вставкой исполняется за О(n+d), где d - количество перестановок
  4. Более эфективный чем Сортировка выбором или Пузырьковая сортировка
  5. Сортировка на месте
  6. Может сортировать даные на лету

Алгоритм:

Каждое повторение алгоритма удаляет элемент с массива и вставляет его в нужное место в уже отсортированном массиве. И эти шаги продолжаются до тех пор пока не останется неотсортированных элементов. Результирующий массив после k итераций имеет следующее свойство: предыдужие k+1 элементов являются отсортированными.

Так же пример того, как работает алгоритм вы можете увидеть на следующей картинке:

Илюстрация алгоритма сортировки вставками

Реализация на Java:

/*
* Insertion sort
*/
public static void insertingSort(Integer[] vector) {
 int key;
 int i;
 for(int j = 1; j < vector.length; j++) {
  key = vector[j];
  i = j - 1; 
  while(i >= 0 && vector[i] > key) {
   vector[i+1] = vector[i];
   i = i - 1;
  }
  vector[i+1] = key;
 }
}
LikeMe: