Игра с кодом: сортировка вставками в Swift

Следующая статья поможет вам: Игра с кодом: сортировка вставками в Swift

Вернуться в блог

Давайте поиграем с кодом! В этом уроке мы обсудим, как работает сортировка вставками. Это один из самых простых алгоритмов сортировки, которые у нас есть, что делает его идеальным кандидатом для неторопливого кодирования на Swift. Какой лучший способ улучшить свои навыки программирования на Swift, чем возиться с алгоритмами сортировки?

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

При создании приложений вам может потребоваться сортировать данные, с которыми сталкивается пользователь. Например, имена в адресной книге. Вы сортируете список имен от А до Я и представляете его пользователю.

В других случаях сортировка происходит «за кулисами». Многие алгоритмы поиска могут более эффективно искать в списке, например, когда он уже отсортирован. Вы можете себе представить, что Google имеет отсортированный по алфавиту указатель поисковых фраз, поэтому он может быстро найти, какой веб-сайт соответствует поисковому запросу «спортивная обувь».

Алгоритм лучше всего определить как «последовательность шагов, которая принимает входные данные и производит выходные данные». Таким образом, алгоритм сортировки берет коллекцию (массив), обрабатывает ее и возвращает отсортированный массив. В некоторых случаях вы можете предоставить дополнительные параметры, например функцию сравнения.

Важным атрибутом алгоритма сортировки является его временная сложность. Короче говоря, временная сложность выражает время, необходимое для выполнения алгоритма, относительно размера входных данных. Обозначение Big O используется для описания временной (и пространственной) сложности. Эффективный алгоритм сортировки, такой как быстрая сортировка, имеет временную сложность в худшем случае O(n log n).

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

Алгоритм, с которым мы сегодня работаем — сортировка вставками — имеет сложность O(n2). Когда размер входного массива удваивается, время, необходимое для выполнения алгоритма сортировки вставками, увеличивается в четыре раза! Вы можете себе представить, что это проблема для больших наборов данных, но для такого упражнения это вполне нормально.

Давайте начнем с сортировки вставками!

Сортировку вставками проще всего сравнить с сортировкой руки (или колоды) игральных карт.

Представьте, что у вас на руках 5 игральных карт. Чтобы отсортировать свои карты, вы достаете карту и определяете ее отсортированное место среди остальных карт. Вы делаете это для каждой карты, чтобы отсортировать всю свою руку.

Именно отсюда сортировка вставками получила свое название, потому что вы извлекаете элементы и помещаете их обратно на отсортированные места. Для каждого элемента массива мы определяем его отсортированное место и вставляем туда элемент.

Давайте обсудим алгоритм сортировки вставками. Мы собираемся отсортировать этот массив целых чисел:

[70, 36, 40, 95, 22, 55, 26]

Мы пройдемся по каждому элементу массива слева направо, кроме первого элемента. Элементы, которые мы уже отсортировали, окажутся слева от массива.

Вот как это работает:

• Мы перебираем каждый элемент массива слева направо. Мы можем пропустить первый элемент, поскольку это уже отсортированный подсписок.
• Каждый элемент сравнивается с подсписком элементов, которые мы уже отсортировали, справа налево, начиная с текущего элемента.
• Когда алгоритм встречает число, большее текущего элемента, это число сдвигается на одну позицию вправо.
• Когда он встречает число, меньшее текущего элемента, или когда мы достигли конца подсписка, вставляется текущий элемент.

Давайте посмотрим на визуальный пример:

На каждом этапе сверху вниз оранжевый элемент сравнивается с синими элементами и вставляется в нужное место. Итак… какое место правильное?

Рассмотрим подробнее шаг 5. Число 55 необходимо вставить куда-нибудь в отсортированный подсписок. Как?

Вот что происходит:

1. Сначала мы уберем 55 человек. Это освобождает место в массиве.
2. Затем мы сравниваем 55 с 95, элементом перед ним. 95 больше 55, поэтому сдвигаем 95 на одну позицию вправо – в свободное пространство.
3. Затем мы сравниваем 55 с 70. 70 больше 55, поэтому мы сдвигаем 70 на одну позицию вправо. (Тот же шаг, что и раньше.)
4. Затем мы сравниваем 55 с 40. 40 меньше 55, поэтому теперь мы вставляем 55 в свободное место.
5. Сделанный! Подходящее место для 55 — между 40 и 70.

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

Почему мы можем пропустить первый пункт? Несмотря на то, что число 70 не находится на последней отсортированной позиции, оно будет сдвинуто вправо из-за сравнения с другими числами. Итак, можно сказать, что подсписок из одного элемента уже отсортирован!

Пришло время закодировать этот алгоритм. Давайте займемся этим!

Основываясь на обнаруженном нами механизме, мы можем шаг за шагом запрограммировать алгоритм сортировки вставками. Большинство деталей уже на месте!

Начнем с неотсортированных чисел. Так:

числа вар = [70, 36, 40, 95, 22, 55, 26]

Теперь нам нужен код для перебора этих чисел, начиная со второго элемента массива и до конца массива. Вот как:

для индекса в 1..

индекс, который представляет собой номер индекса массива, который мы в данный момент итерируем

значение, которое является значением массива, который мы сейчас проверяем.

позиция — индекс, в который мы собираемся вставить значение (после того, как мы определили, что это за отсортированная позиция)

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

в то время как позиция > 0 && числа[position – 1] > значение {
цифры[position] = числа[position – 1]
позиция -= 1
}

Это цикл while. Он будет продолжать цикл, пока его выражение истинно. Это идеально, если вы не знаете, сколько раз нужно выполнить цикл (в отличие от цикла for).

Как работает цикл while?

• Помните, что, перебирая числа, мы собираемся проверять подсписок отсортированных чисел перед ним.
• Мы сделаем это, начав с индекса и считая в обратном порядке, пока не достигнем 0. Это первая часть цикла. Пока позиция выше нуля, вычтите 1 из позиции с позицией -= 1.
• Но это еще не все! Мы хотим вернуться назад только в том случае, если число в проверяемой позиции больше текущего значения.
• Это вторая часть цикла. Если проверяемое число больше числа в текущей позиции, сдвиньте эту позицию на одну позицию вправо с помощью чисел.[position] = числа[position – 1].

Наконец, как только отсортированная позиция текущего элемента определена, мы можем просто присвоить значение его новому месту. Так:

цифры[position] = значение

Элементы, превышающие значение, были сдвинуты вправо. И цикл while останавливается, когда обнаруживает значение, меньшее текущего значения. Таким образом, теперь мы можем вставить текущее значение в свободное пространство.

Это самый сложный шаг в этом алгоритме. Стоит посмотреть еще раз!

Давайте проверим это с другой точки зрения. Вы знаете, что сортировка вставками опирается на три принципа:

• Определите отсортированную позицию для каждого элемента массива, перебирая массив.
• Смещая элементы, которые больше текущего элемента, вправо
• Пока элемент не станет меньше текущего, просто вставьте его.

Цикл while делает две вещи. Он отслеживает позицию и сдвигает элементы массива вправо. Это происходит только в том случае, если позиция больше нуля («ограничитель обратного хода») и если проверяемое значение больше текущего значения.

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

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

Вы оглядываетесь назад, чтобы сравнить это число со всеми числами, которые вы ранее отсортировали. Вы не можете просто вставить число, поэтому, чтобы освободить место, вы сдвигаете предыдущие числа к себе, пока не освободите место в нужном месте.

Вот алгоритм, который мы закодировали на данный момент. Попробуйте! Вы понимаете, как это работает?

числа вар = [70, 36, 40, 95, 22, 55, 26]

для индекса в 1.. 0 && числах[position – 1] > значение {
цифры[position] = числа[position – 1]
позиция -= 1
}

цифры[position] = значение
}

распечатать (цифры)

Вот небольшой вопрос: можете ли вы изменить один символ, чтобы вместо этого алгоритм сортировки сортировался от наибольшего числа к наименьшему?

А вот тот же алгоритм, с добавленными подробными строками print(), которые помогут вам пройти все этапы. Попробуйте!

числа вар = [70, 36, 40, 95, 22, 55, 26]

print(“Мы собираемся отсортировать эти числа: \(numbers)”)

для индекса в 1.. 0 && числах[position – 1] > ценность
{
print(“– \(числа[position-1]) > \(значение), поэтому сдвиг \(числа[position-1]) Направо”)

цифры[position] = числа[position – 1]
позиция -= 1

print(“-> \(числа)”)
}

print(“– Найдена отсортированная позиция \(value) равна \(position), поэтому вставляем”)

цифры[position] = значение

print(“-> \(числа)”)
Распечатать(“”)
}

распечатать (цифры)

Конечно, большой вопрос: можем ли мы превратить этот алгоритм в функцию, работающую с любым типом данных?

Да! Пока входные данные для алгоритма соответствуют протоколу Comparable, вы можете сортировать все, что захотите. И на всякий случай мы даже добавим сравнение.

Вот так:

функция вставкиSort (_ вход: [T]для сравнения: (T, T) -> Bool) -> [T]
{
вар элементы = ввод

для индекса в 1.. 0 && сравнение(элементы[position – 1]ценить) {
предметы[position] = предметы[position – 1]
позиция -= 1
}

предметы[position] = значение
}

возврат товаров
}

var sorted = InsertionSort([70, 36, 40, 95, 22, 55, 26]автор: >)
распечатать (отсортировано)

имена переменных = InsertionSort([“Marvin”, “Arthur”, “Zaphod”, “Trillian”, “Eddie”], by: { $0 < $1 }) print(names) Что здесь происходит? Алгоритм сортировки вставками не изменился, но произошли некоторые изменения:

• Функция InsertionSort(_:by:) использует общий заполнитель T. А тип T должен соответствовать Comparable, например Int или String.
• Тип входного параметра и тип возвращаемого значения функции оба являются [T]. Какой бы тип вы ни вставили, он тоже выйдет. Конечно, они оба массивы.
• Параметр сравнения принимает замыкание типа (T, T) -> Bool. Это означает, что замыкание имеет два входа T и возвращает логическое значение.

В алгоритме мы вызываем замыкание сравнения и предоставляем ему два значения, которые необходимо сравнить. Помните, как мы использовали это сравнение для управления сортировкой в ​​алгоритме? Благодаря замыканию теперь вы можете предоставить собственную функцию сравнения!

Вы увидите это для отсортированных массивов и массивов имен в конце. Для сортировки мы просто предоставляем логический оператор «больше чем >». Этот оператор принимает два входных значения, левую и правую части, и возвращает логическое значение. Реализация по сути точно такая же, как и раньше.

А для имен мы предоставляем замыкание { $0 < $1 }. Он использует сокращение $n для ссылки на входные параметры замыкания и сравнивает их с логическим оператором «меньше <». Как и раньше, два элемента массива сравниваются друг с другом, чтобы определить порядок их сортировки.

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