Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Сортировка вставками - алгоритм, который сортирует данные путём изменения их позиции, исходя из значения элемента, стоящего слева.

---

Принцип работы алгоритма

Сортировка вставками проходит по каждому элементу последовательности и сравнивает его со стоящим слева элементом. Если выбранный элемент больше, то они меняются местами, пока элемент слева не станет меньше или равен выбранному. Иначе - алгоритм переходит к следующему элементу.

---

Схематическая работа алгоритма

Есть неотсортированная последовательность данных

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2  4  6  5  1  3 Необходимо перебрать все элементы, начиная со второго, и сравнить текущий элемент с тем, что находится левее.

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2  4  6  5  1  3

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2   4< В случае, если текущий элемент больше или равен стоящему слева, алгоритм переходит дальше. Иначе - меняет их местами до тех пор, пока число слева не будет меньше или равно текущему.

В данном случае, на этом этапе, выбран элемент "4", он не больше стоящего слева, поэтому алгоритм переходит к следующему элементу.

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2  4  6  5  1  3

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      4   6<

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2  4  6  5  1  3

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      6   5> На третьем этапе алгоритм дошёл до ситуации, когда текущий элемент меньше стоящего слева, поэтому алгоритм меняет их местами.

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2  4  6  5  1  3

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2  4  5  6  1  3

Необходимо повторить сравнение, чтобы удостовериться, что элемент стоит на верной позиции.

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2  4  5  6  1  3

Текущий элемент больше стоящего слева, алгоритм переходит к следующему этапу.

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2  4  5  6  1  3 На этом этапе алгоритм дошел до элемента - "1".

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      6   1>

Этот элемент меньше всех элементов, стоящих слева, поэтому он отправляется в самое начало массива.

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2  4  5  6  1  3

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      1  2  4  5  6  3

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      1  2  4  5  6  3

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      1  2  4  5  6  3

Последний элемент, который нужно отсортировать - "3".

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      6   3>

Текущий элемент меньше стоящего слева, поэтому он перемещается согласно алгоритму.

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      1  2  4  5  6  3

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      1  2  3  4  5  6

Перемещения больше не требуются, потому что текущий элемент больше стоящего слева.

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      2   3<

Получим отсортированный массив:

     

       

          @font-face {

            font-family: "Virgil";

            src: url("https://excalidraw.com/Virgil.woff2");

          }

          @font-face {

            font-family: "Cascadia";

            src: url("https://excalidraw.com/Cascadia.woff2");

          }

       

     

      1  2  3  4  5  6

Вычислительная сложность

Вычислительная сложность $O(n^2)$ достигается перебором всех данных и перемещением их части на иные позиции.

---

Псевдокод

Функция сортировка_вставками(данные, количество_данных)
    Для индекса числа в диапазоне от 0 до количества данных
        текущий индекс <- индекс числа
        текущее число <- данные по текущему индексу
        предыдущее число <- данные по текущему индексу - 1
        Пока ( текущий индекс > 0 ) И ( текущее число < предыдущее число )
            Меняем местами текущее число и предыдущее число
            текущий индекс <- текущий индекс - 1
            
    Вернуть данные

---

Реализация на Python

Аннотация:
insert_sort - функция сортировки вставками
array - сортируемый массив
data_length - длина массива 
number_index - индекс текущего элемента массива для вставки 
current_index - индекс элемента, который сравнивается и перемещается в отсортированной части массива

def insert_sort(array, data_length):
    for number_index in range(1, data_length):
        current_index = number_index
        while current_index > 0 and array[current_index] < array[current_index - 1]:
            array[current_index], array[current_index - 1] = array[current_index - 1], array[current_index]
            current_index -= 1

    return array

---

Олимпиадная реализация на C++

Аннотация:
ins_sort - функция сортировки вставками
arr - сортируемый массив
len - длина массива
i - текущий индекс основного цикла
j - индекс внутреннего цикла, используется для перемещения элементов
tmp - временная переменная для хранения текущего элемента

int* ins_sort(int *arr, int len) {
    for (int i = 1; i < len; i++) {
        int j = i;
        int tmp = arr[i];
        while (j > 0 && tmp < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = tmp;
    }
    return arr;
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
comparation - функция сравнения
firstData - первый элемент для сравнения
secondData - второй элемент для сравнения
InsertionSort - функция сортировки вставками
array - сортируемый массив
array_size - размер массива
comparison - результат функции сравнения элементов
numberIndex - текущий индекс основного цикла
currentIndex - индекс внутреннего цикла, который используется для перемещения элементов
tmp - временная переменная для хранения текущего элемента

template <class Iter, class Comp>
void InsertionSort(Iter begin, Iter end, Comp comp = Comp()) {
    for (auto i = begin; i != end; ++i) {
        auto best = i;
        for (auto j = std::next(i); j != end; ++j)
            if (comp(*j, *best))
                best = j;
        std::iter_swap(i, best);
    }
}