Сортировка вставками — это простой и эффективный алгоритм сортировки, который работает путем перебора массива и вставки каждого элемента на свое место в отсортированной части массива. Это делается путем сравнения элемента с его соседями и сдвига их по мере необходимости, чтобы освободить место для вставляемого элемента.
В этом руководстве мы узнаем, как реализовать сортировку вставками в 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 и как она работает. Удачного кодирования!