[Перевод] Визуализация 5 алгоритмов сортировки на Python
Реализация алгоритмов сортировки: выбором, пузырьком, вставками, слиянием и быстрой сортировкой с помощью Python.
Введение
Сортировка массивов часто используется в программировании, чтобы помочь понять данные и выполнить поиск. Поэтому скорость сортировки больших объемов информации крайне важна для функциональных проектов и оптимизации времени работы. Есть много алгоритмов для упорядочения объектов.
В статье вы посмотрите на реализацию и визуализацию пяти популярных алгоритмов сортировки. Код написан на Python, а графический интерфейс построен на Tkinter.
Эти 5 алгоритмов включают:
Сортировка выбором
Сортировка пузырьком
Сортировка вставками
Сортировка слиянием
Быстрая сортировка quicksort
Визуализация массива
Рис. 1 — пример массива неупорядоченных целочисленных данных
Как только класс предоставляет перегруженные реализации операторов сравнения, он сортируется. На Python это:
_lt_: меньше чем
_gt_: больше чем
_eq_: равно
Код ниже демонстрирует перегруженный метод меньше чем.
def __lt__(self, other):
# compare object with "other" object of same type
return self.value < other.valueДавайте представим числовые данные с помощью столбцов. Высота столбца i равна значению элемента массива i. У них всех одинаковая ширина. Такое изображение списка числовых значений с Рис. 1 в виде столбцов приведено на Рис. 2.
Рис 2. Значения Целых числе в виде высот столбцов
Сортировка числовых данных по убыванию или по возрастанию требует соответствующей перестановки значений. Для анимации каждого алгоритма с данными, требуется обновлять диаграмму после замены отдельных элементов.
Ниже — код Python для замены двух элементов в списке.
def swap(arr, a, b):
""" переставляем элементы a и b в массиве """
temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
# возвращаем массивДля рендеринга необходимы два класса: Canvas, и Bar. Код с комментариями для полного пользовательского интерфейса лежит в репозитории GitHub.
Ниже показан необходимый код для отображения обновлений в классе Canvas. Если bar index меняется, как указано выше, setter запускает функцию update_bar на основном холсте. После запуска обновления элементы массива меняются местами.
@index.setter
def index(self, i):
""" update coordinates when index changes """
self._index = i
# update horizontal coordinates
self.x1 = self._index * self.width
self.x2 = self.x1 + self.width
# dispatch updates to subscriber (visualiser)
self.subscriber.update_bar(self)Сортировка выбором
Встроенный алгоритм сортировки, то есть отсортированные элементы используют то же хранилище, что и исходные элементы.
Ниже — реализация сортировки выбором на Python с подробными комментариями.
Внешний цикл производит итерации по всей длине несортированного массива. В это время внутренний цикл ищет минимальное значение в оставшейся части набора данных. Затем происходит единая замена, переставляющая элемент под номером i и элемент min_index.
def selection_sort(self, unsorted, n):
# итерируемся по массиву
for i in range(0, n):
# инициализируемся первым значеним
current_min = unsorted[i]
# инициализируем минимальный индекс
min_index = i
# итерируемся по оставшимся элементам массива
for j in range(i, n):
# проверяем, если j-тое значение меньше текушего минимального
if unsorted[j] < current_min:
# обновляес минимальные значение и индекс
current_min = unsorted[j]
min_index = j
# меняем i-тое и j-тое значения
swap(unsorted, i, min_index)Метод сортировки выбором обычно включает параметры:
Временная сложность = O (n²).
n² итераций очевидны из двух вложенных циклов.Пространственная сложность = O (1).
Как упоминалось выше, сортировка происходит в том же массиве, поэтому использование памяти не зависит от данных обработки.
Рис. 3 — сортировка выбором
Сортировка пузырьком
Несколько раз проходит по списку, сравнивая соседние элементы. Элементы меняются местами в зависимости от условия сортировки.
Ниже показана реализация сортировки выбором на Python с комментариями.
def bubble_sort(self, unsorted, n):
""" алгоритм сортировки пузырьком """
# итерируемся по неотсорт. массиву до предпоследнего элемента
for i in range(0, n - 1):
# проставляем условия флага для финального списка
swapped = False
# итерируемся по осташвимся неотсортированным объектам
for j in range(0, n - 1 - i):
# сравниваем соседние элементы
if unsorted[j].value > unsorted[j + 1].value:
# меняем элементы местами
swap(unsorted, j, j + 1)
swapped = True
# завершаем алгоритм, если смены не произошло
if not swapped:
breakОбратите внимание, что из всех алгоритмов у сортировки пузырьком наихудший случай и среднее значение:
Временная сложность = O (n²).
Внутренний цикл работает не менее n раз. Поэтому операция займет не менее n² времениПространственная сложность = O (1).
Дополнительная память не используется, потому что происходит обмен элементов в исходном массиве
Большие значения всплывают, как пузырьки, в верхнюю часть списка по мере выполнения программы, как показано на Рис. 4.
Рис. 4 — Сортировка пузырьком
Сортировка вставками
Строит конечный массив по одному элементу за раз. Используйте код, указанный ниже для выполнения метода над несортированным массивом объектов.
def insertion_sort(unsorted, n):
""" сортировка вставками """
# итерация по неотсортированным массивам
for i in range(1, n):
# получаем значение элемента
val = unsorted[i].value
# записываем в hole индекс i
hole = i
# проходим по массиву в обратную сторону, пока не найдём элемент больше текущего
while hole > 0 and unsorted[hole - 1].value > val:
# переставляем элементы местами , чтобы получить правильную позицию
unsorted[hole].value = unsorted[hole - 1].value
# делаем шаг назад
hole -= 1
# вставляем значение на верную позицию
unsorted[hole].value = valУ сортировки вставками есть наихудший случай:
Временная сложность = O (n²). Как внешний цикл for, так и внутренний while работают приблизительно n раз
Пространственная сложность = O (1). Операции проводятся с исходным массивом. Таким образом, дополнительной памяти не требуется.
Рис. 5 — Сортировка вставками
Сортировка слиянием
Сортировка слиянием — алгоритм сортировки по принципу «разделяй и властвуй». Задача раскладывается на более мелкие аналогичные подзадачи до тех пор, пока не будет решен базовый случай.
Несортированный массив разделяется до тех пор, пока не выделится базовый случай отдельных элементов. Затем происходит сравнение между временными массивами, перемещающимися обратно вверх по стеку рекурсии.
def divide(self, unsorted, lower, upper):
""" рекурсивная функция для разделения массива на два подмассива для сортировки """
# с помощью рекурсии достигнут базовый случай
if upper <= lower:
return
# получаем среднее значение для разделения
mid = (lower + upper) // 2
# делим массив посередине
divide(unsorted, lower, mid)
divide(unsorted, mid + 1, upper)
# склеиваем отсортированные массивы
merge(unsorted, lower, mid, mid + 1, upper)
def merge(unsorted, l_lower, l_upper, r_lower, r_upper):
""" merging two sorted arrays to one sorted array """
# извлекаем левый и правый индексы
i, j = l_lower, r_lower
# инициализируем временный массив
temp = []
# проходим по индексам
while i <= l_upper and j <= r_upper:
# определяем, какое значение следующим вставить во временный массив
if unsorted[i].value <= unsorted[j].value:
temp.append(unsorted[i])
i += 1
else:
temp.append(unsorted[j])
j += 1
# одно из условий выше заканчивается первым
# поэтому обрабатываем незаконченный случай
while i <= l_upper:
temp.append(unsorted[i])
i += 1
while j <= r_upper:
temp.append(unsorted[j])
j += 1
# присваиваем значения из временного массива
for y, k in enumerate(range(l_lower, r_upper + 1)):
unsorted[k] = temp[y]У сортировки слиянием есть:
Временная сложность = O (nlog (n)). У алгоритмов сортировки «разделяй и властвуй» такая временная сложность. Эта сложность — наихудший сценарий для подобных алгоритмов.
Пространственная сложность = O (n), если выделение памяти увеличивается не быстрее константы kN, т.е. кратной размеру набора данных.
Рис. 6 — Сортировка слиянием
Быстрая сортировка
Быстрая сортировка примерно в два-три раза быстрее основных конкурентов, сортировки слиянием и пирамидальной сортировки. Ее часто реализуют рекурсивно, как на примере ниже.
Значения pivot лежат в основе алгоритма быстрой сортировки. По существу, pivot опорные значения. Постановка pivot означает, что объекты слева всегда меньше, а элементы справа больше, чем pivot.
def quick_sort(self, unsorted, start, end):
""" быстрая сортировка """
# останавливаемся, когда индекс слева достиг или превысил индек справа
if start >= end:
return
# определяем позицию следующего пивота
i_pivot = partition(unsorted, start, end - 1)
# рекурсивный вызов левой части
quick_sort(unsorted, start, i_pivot)
# рекурсивный вызов правой части
quick_sort(unsorted, i_pivot + 1, end)
def partition(self, unsorted, start, end):
""" arrange (left array < pivot) and (right array > pivot) """
# выбираем значение pivot как последний элемент неотсортированного сегмента
pivot = unsorted[end]
# назначаем на pivot значение левого индекса
i_pivot = start
# проходим от начала до конца текущего сегмента
for i in range(start, end):
# сравниваем текущее значение со значением pivot
if unsorted[i].value <= pivot.value:
# меняем местами текущее значение и значенрие pivot
swap(unsorted, i, i_pivot)
# увеличиваем значение пивота
i_pivot += 1
# ставим пивот в правильную позицию, заменив со значением слева
swap(unsorted, i_pivot, end)
# возвращаем следующее значение пивота
return i_pivotРекурсивно разбивая массив, выбирая точки pivot и назначая их в правильном месте, получаем окончательно отсортированный массив.
У быстрой сортировки есть среднее значение:
Временная сложность = O (n*log (n)). Как и сортировка слиянием, данная нотация определяется по принципу разделяй и властвуй или быстрой сортировки. Наихудший сценарий — O (n²). Однако это происходит, только когда элементы массива правильно восходят или нисходят.
Рис. 7 — Быстрая сортировка
Заключение
Оптимизированная сортировка имеет критически важное значение для разработки ПО. Временные сложности конкретных алгоритмов могут варьироваться в зависимости от первоначальногопорядка элементов. Однако наиболее целесообразно предположитьнаихудший сценарий.
В статье мы не рассмотрели некоторые другие методы. Например, пирамидальная , поразрядная сортировка и любимый неэффективный алгоритм случайной сортировки.
Выше представлен код Python и визуализации пяти стандартных алгоритмов сортировки. Понимание данных механизмов ценно для студентов, изучающих компьютерные науки, поскольку некоторые процедуры часто появляются на собеседованиях.
