Сортировка вставками — это простой и эффективный алгоритм сортировки, который работает путем перебора массива и вставки каждого элемента на свое место в отсортированной части массива. Это делается путем сравнения элемента с его соседями и сдвига их по мере необходимости, чтобы освободить место для вставляемого элемента.

В этом руководстве мы узнаем, как реализовать сортировку вставками в Swift, и поймем, как это работает, на примере.

Выполнение:

Чтобы реализовать сортировку вставками в Swift, мы создадим функцию, которая принимает массив целых чисел в качестве аргумента и возвращает отсортированную версию этого массива.

Вот код нашей функции сортировки вставками:

func insertionSort(_ array: [Int]) -> [Int] {
    var sortedArray = array
    for i in 1..<sortedArray.count {
        let current = sortedArray[i]
        var j = i - 1
        while j >= 0 && sortedArray[j] > current {
            sortedArray[j+1] = sortedArray[j]
            j -= 1
        }
        sortedArray[j+1] = current
    }
    return sortedArray
}

Теперь давайте разберем, как работает эта функция.

Сначала мы создаем изменяемую копию входного массива и присваиваем ее переменной с именем sortedArray. Это связано с тем, что мы будем изменять массив по мере его сортировки, и мы не хотим изменять исходный входной массив.

Далее у нас есть цикл for, который перебирает все элементы массива, начиная со второго элемента (индекс 1). Для каждой итерации мы присваиваем текущий элемент переменной с именем current и присваиваем индекс предыдущего элемента переменной с именем j.

Внутри цикла for у нас есть цикл while, который продолжается до тех пор, пока j больше или равно 0, а элемент с индексом j больше current. Этот цикл while сдвигает элементы вправо, чтобы освободить место для вставляемого элемента.

Наконец, вне цикла while вставляем рассматриваемый элемент (current) на подобающее ему место, присваивая ему индекс j+1.

Пример:

Давайте рассмотрим пример, чтобы увидеть, как сортировка вставками работает с небольшим массивом.

Предположим, у нас есть следующий массив: [5, 2, 4, 1, 3]

Первый элемент (5) уже отсортирован, поэтому переходим ко второму элементу (2). Мы сравниваем 2 с его соседями (5 и 4) и обнаруживаем, что он меньше их обоих. Мы сдвигаем 5 и 4 вправо, чтобы освободить место для 2, в результате чего получается следующий массив: [2, 5, 4, 1, 3]

Далее переходим к третьему элементу (4). Мы сравниваем 4 с его соседями (5 и 2) и обнаруживаем, что оно больше 2, но меньше 5. Сдвигаем 5 вправо, чтобы освободить место для 4, в результате чего получается следующий массив: [2, 4, 5, 1 , 3]

Мы продолжаем этот процесс, пока не достигнем последнего элемента (3). Мы сравниваем 3 с его соседями (1 и 5) и обнаруживаем, что оно больше 1, но меньше 5. Сдвигаем 5 вправо, чтобы освободить место для 3, в результате чего получается следующий массив: [1, 2, 3, 4 , 5]

На данный момент массив полностью отсортирован, и функция возвращает отсортированный массив: [1, 2, 3, 4, 5]

Заключение:

В заключение, сортировка вставками — это простой, но эффективный алгоритм сортировки, который работает путем перебора массива и вставки каждого элемента на свое место в отсортированной части массива. Это полезный алгоритм для сортировки небольших массивов или для сортировки уже частично отсортированных массивов.

Для получения дополнительной информации о сортировке вставками и других алгоритмах сортировки вы можете обратиться к документации Swift по сортировке и странице Википедии по алгоритмам сортировки.

Я надеюсь, что этот учебник был полезен для понимания того, как реализовать сортировку вставками в Swift и как она работает. Удачного кодирования!