Быстрая сортировка python реализация

Быстрая сортировка в 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)

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

Источник

Визуализация 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 

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