Визуализация 5 алгоритмов сортировки на Python
Реализация алгоритмов сортировки: выбором, пузырьком, вставками, слиянием и быстрой сортировкой с помощью Python.
Введение
Сортировка массивов часто используется в программировании, чтобы помочь понять данные и выполнить поиск. Поэтому скорость сортировки больших объемов информации крайне важна для функциональных проектов и оптимизации времени работы. Есть много алгоритмов для упорядочения объектов.
В статье вы посмотрите на реализацию и визуализацию пяти популярных алгоритмов сортировки. Код написан на Python, а графический интерфейс построен на Tkinter.
Эти 5 алгоритмов включают:
- Сортировка выбором
- Сортировка пузырьком
- Сортировка вставками
- Сортировка слиянием
- Быстрая сортировка quicksort
Визуализация массива
Как только класс предоставляет перегруженные реализации операторов сравнения, он сортируется. На Python это:
Код ниже демонстрирует перегруженный метод меньше чем.
def __lt__(self, other): # compare object with "other" object of same type return self.value < other.valueДавайте представим числовые данные с помощью столбцов. Высота столбца i равна значению элемента массива i. У них всех одинаковая ширина. Такое изображение списка числовых значений с Рис. 1 в виде столбцов приведено на Рис. 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).
Как упоминалось выше, сортировка происходит в том же массиве, поэтому использование памяти не зависит от данных обработки.
Сортировка пузырьком
Несколько раз проходит по списку, сравнивая соседние элементы. Элементы меняются местами в зависимости от условия сортировки.
Ниже показана реализация сортировки выбором на 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.
Сортировка вставками
Строит конечный массив по одному элементу за раз. Используйте код, указанный ниже для выполнения метода над несортированным массивом объектов.
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). Операции проводятся с исходным массивом. Таким образом, дополнительной памяти не требуется.
Сортировка слиянием
Сортировка слиянием — алгоритм сортировки по принципу «разделяй и властвуй». Задача раскладывается на более мелкие аналогичные подзадачи до тех пор, пока не будет решен базовый случай.
Несортированный массив разделяется до тех пор, пока не выделится базовый случай отдельных элементов. Затем происходит сравнение между временными массивами, перемещающимися обратно вверх по стеку рекурсии.
def divide(self, unsorted, lower, upper): """ рекурсивная функция для разделения массива на два подмассива для сортировки """ # с помощью рекурсии достигнут базовый случай if upper У сортировки слиянием есть:
- Временная сложность = O(nlog(n)). У алгоритмов сортировки «разделяй и властвуй» такая временная сложность. Эта сложность – наихудший сценарий для подобных алгоритмов.
- Пространственная сложность = O(n), если выделение памяти увеличивается не быстрее константы kN, т.е. кратной размеру набора данных.
Быстрая сортировка
Быстрая сортировка примерно в два-три раза быстрее основных конкурентов, сортировки слиянием и пирамидальной сортировки. Ее часто реализуют рекурсивно, как на примере ниже.
Значения 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 и назначая их в правильном месте, получаем окончательно отсортированный массив.
У быстрой сортировки есть среднее значение:
Временная сложность = O(n*log(n)). Как и сортировка слиянием, данная нотация определяется по принципу разделяй и властвуй или быстрой сортировки. Наихудший сценарий – O(n²). Однако это происходит, только когда элементы массива правильно восходят или нисходят.
Заключение
Оптимизированная сортировка имеет критически важное значение для разработки ПО. Временные сложности конкретных алгоритмов могут варьироваться в зависимости от первоначальногопорядка элементов. Однако наиболее целесообразно предположитьнаихудший сценарий.
В статье мы не рассмотрели некоторые другие методы. Например, пирамидальная , поразрядная сортировка и любимый неэффективный алгоритм случайной сортировки.
Выше представлен код Python и визуализации пяти стандартных алгоритмов сортировки. Понимание данных механизмов ценно для студентов, изучающих компьютерные науки, поскольку некоторые процедуры часто появляются на собеседованиях.
Другие наши статьи по бэкенду и асинхронному программированию для начинающих:
Другие наши статьи по бэкенду и асинхронному программированию для продвинутого уровня:
💻Асинхронное программирование на Python для джуниор-разработчиков💻
Асинхронное программирование используется для высоконагруженных проектов и микросервисов. Его спрашивают на собеседованиях в технологически развитых компаниях, и оно открывает дорогу к работе в интересных проектах. Если вы уже пишете на Python, но пока не изучили модуль Asyncio, приглашаю вас на курс по асинхронному программированию на Python.
- Разберётесь, как работает асинхронное программирование и где его лучше применять.
- Получите опыт работы с микросервисами.
- Освоите стандартную python-библиотеку Asyncio, напишите чат-бота и event loop.
👉 Посмотреть программу и записаться на курс: https://vk.cc/cmUy1v
Быстрая сортировка в Python
Идея быстрой сортировки была придумана информатиком Чарльзом Хоаром в 1960 году. Рассмотрим её преимущества над пузырьковой сортировкой и реализуем алгоритм в Python.
Одно из первых заданий программиста в любом языке программирования — разработка алгоритма сортировки массива. Большинство выбирает пузырьковый метод, то есть упорядочивание элементов после сравнения друг с другом. В Python это выглядит так:
nums = [4, 1, 6, 3, 2, 7, 8] n = 1 while n len(nums): for i in range(len(nums) - n): if nums[i] > nums[i + 1]: nums[i], nums[i + 1] = nums[i + 1], nums[i] n += 1
Однако на практике он неэффективен, так как предполагает многократное прохождение по всему массиву. Альтернативный метод, впоследствии получивший название «быстрая сортировка», изобрел информатик Чарльз Хоар в 1960. Он предполагает деление массива на две части, в одной из которых находятся элементы меньше определённого значения, в другой – больше или равные. Рассмотрим реализацию в Python быстрой сортировки Хоара.
def quicksort(nums): if len(nums) 1: return nums else: q = random.choice(nums) s_nums = [] m_nums = [] e_nums = [] for n in nums: if n q: s_nums.append(n) elif n > q: m_nums.append(n) else: e_nums.append(n) return quicksort(s_nums) + e_nums + quicksort(m_nums)
В идеале, выбранный элемент должен быть медиальным, но для его поиска пришлось бы запускать ещё один цикл. Наша реализация на питоне сортировки Хоара использует случайный элемент, но она тоже не идеальна: в случае, если выбрано первое или последнее число, а массив отсортирован, то на питоне быстрая сортировка будет совпадать по эффективности с пузырьковой.
Впрочем, описанный алгоритм можно прокачать, сократив количество используемой памяти:
def quicksort(nums, fst, lst): if fst >= lst: return i, j = fst, lst pivot = nums[random.randint(fst, lst)] while i j: while nums[i] pivot: i += 1 while nums[j] > pivot: j -= 1 if i j: nums[i], nums[j] = nums[j], nums[i] i, j = i + 1, j - 1 quicksort(nums, fst, j) quicksort(nums, i, lst)
В этом случае вы используете память только для организации рекурсии и в Python быстрая сортировка становится по-настоящему «быстрой». В заключении темы опишем на питоне сортировку Хоара в функциональном виде:
def quicksort(nums): if len(nums) 1: return nums else: q = random.choice(nums) l_nums = [n for n in nums if n q] e_nums = [q] * nums.count(q) b_nums = [n for n in nums if n > q] return quicksort(l_nums) + e_nums + quicksort(b_nums)
Также важно упомянуть, что в питоне методов сортировки чисел в массиве – множество, практически в каждой библиотеке, предназначенной для работы с числами. Однако знать и понимать описанные – важно не только для общего развития, но и для прохождения собеседований. Там это один из самых популярных вопросов.