Сортировка включением(метод вставки).

Алгоритм:

· Массив делится на две части: в первой все элементы отсортированы, во второй нет. На первом шаге считаем, что первый элемент массива отсортирован.

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

Сложность: .

Алгоритм устойчивый.

Сортировка на том же месте.

Эффективен на небольших наборах данных.

Эффективен на наборах данных, которые уже частично отсортированы;

Может сортировать список по мере его получения.

Может быть реализована с помощью списков.

Сортировка Шелла.

Алгоритм:

· Является усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами.

· При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии (для разных размеров массивов, выбираются различные последовательности ). После этого процедура повторяется для некоторых меньших значений, а завершается сортировка Шелла упорядочиванием элементов при (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места.

Эффективен на любых наборах данных.