Сортировка вставкой - это простой алгоритм сортировки, который строит конечный отсортированный массив по одному элементу за раз. Он гораздо менее эффективен на больших списках, чем более продвинутые алгоритмы, но может быть полезен в некоторых случаях, когда список почти отсортирован или когда размер задачи невелик.
Вот пример реализации алгоритма сортировки вставкой в Go:
В данной реализации функция insertionSort() принимает на вход несортированный массив целых чисел и возвращает тот же массив в отсортированном порядке, используя алгоритм сортировки вставкой.
Алгоритм работает путем итерации массива от второго элемента (т.е. индекс 1) до последнего элемента (т.е. индекс len(arr)-1). Для каждого элемента алгоритм сравнивает его с предыдущими элементами и перемещает его на нужную позицию в отсортированном массиве, сдвигая все большие элементы на одну позицию вправо. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован.
Функция insertionSort() возвращает отсортированный массив после завершения работы алгоритма. В основной функции создается несортированный массив, а для его сортировки вызывается функция insertionSort(). Затем отсортированный массив выводится на консоль.