Сортировка вставками
Сортировка вставками
Сортировка вставками – наверное, самый простой способ сортировки. Заключается он в следующем: идём по массиву и как только встречаем нарушение порядка, начинаем перемещать элемент, который нарушил порядок до тех пор, пока он не встанет на место, где не нарушает порядок. Таким образом обходим все элементы.
Пусть мы хотим отсортировать массив 1,9,4,2,8,6
1,9,4,2,8,6
Элементы 1 и 9 идут по порядку. 4 нарушает порядок. Начинаем его «протаскивать» вперёд до тех пор, пока порядок не установится
1,4,9,2,8,6Четвёртый элемент нарушает порядок. Тащим его налево, пока порядок не установится
1,4,2,9,8,6 1,2,4,9,8,6
И так далее
1,2,4,8,9,6 1,2,4,8,6,9 1,2,4,6,8,9
Массив отсортирован.
Каждый элемент, который нарушает порядок вставляется на своё место, поэтому алгоритм получил название сортировки вставками.
typedef int T; #define CMP_GT(a, b) ((a) > (b)) void insertionSort(T *a, size_t size) { size_t i, j; T tmp; for (i = 1; i < size; i++) { if (CMP_GT(a[i - 1], a[i])) { j = i; while (CMP_GT(a[j-1], a[j]) && j > 0) { tmp = a[j - 1]; a[j - 1] = a[j]; a[j] = tmp; j--; } } } }
Сортировка вставками отличается от сортировки пузырьком тем, что мы «сопровождаем» элемент массива и вставляем его на нужное место. В сортировке пузырьком, после обмена местами двух элементов, даже если этот обмен привёл к опять к нарушению порядка, мы всё равно двигаемся дальше.
Сравним, сортировка пузырьком массива 6,5,1,2,4,0
6,5,1,2,4,0 5,6,1,2,4,0 5,1,6,2,4,0 5,1,2,6,4,0 5,1,2,4,6,0 5,1,2,4,0,6 1,5,2,4,0,6 1,2,5,4,0,6 1,2,4,5,0,6 1,2,4,0,5,6 1,2,4,0,5,6 1,2,4,0,5,6 1,2,4,0,5,6 1,2,4,0,5,6 1,2,0,4,5,6 1,2,0,4,5,6
и т.д.
Сортировка вставками
6,5,1,2,4,0 5,6,1,2,4,0 5,1,6,2,4,0 1,5,6,2,4,0 1,5,6,2,4,0 1,5,2,6,4,0 1,2,5,6,4,0 1,2,5,4,6,0 1,2,4,5,6,0 1,2,4,5,0,6 1,2,4,0,5,6 1,2,0,4,5,6 1,0,2,4,5,6 0,1,2,4,5,6
Сортировка вставками в случае работы с отсортированным массивом проходит его всего один раз. Несмотря на сложность порядка n2, сортировка вставками оказывается наиболее эффективной при сортировке массивов маленького размера (единицы, десятки элементов), поэтому используется в сложных алгоритмах сортировки для работы с маленькими массивами. Например, пусть мы используем сортировку слиянием и дошли до состояния, когда размер подмассива равен 8. Его вполне можно отсортировать вставками и передать дальше, как уже отсортированный для слияния.
