Quicksort — популярный алгоритм сортировки, который часто используется. В первой половине этого поста мы будем использовать простые целые числа, но мы покажем, как адаптировать этот метод для сортировки объектов пользовательского класса. Быстрая сортировка представляет собой алгоритмы сортировки «разделяй и властвуй», «на месте» и «нестабильная сортировка». Перед рекурсивной сортировкой больших массивов функция «разделяй и властвуй» делит массив на более короткие массивы, пока не найдет пустой массив, даже содержащий только одну запись. Массив или любые подмассивы не дублируются при использовании на месте. Однако для всех рекурсивных вызовов требуется стековая память. Нестабильный алгоритм сортировки этого не гарантирует; это может случиться, но это не гарантировано. Это в основном актуально при сортировке объектов, а не примитивных видов.
Пример 1
Начнем с выбора опорного элемента. Затем, чтобы перебрать все элементы в списке, мы используем Python для цикла. Если число <= к оси, оно сдвигается влево. В противном случае он смещается в правую сторону от оси вращения. Наша программа Python возвращает новое высокое значение. Item + 1 равняется новому высокому значению. После этого мы должны выполнить наш алгоритм. Для этого можно создать отдельную процедуру. Эта функция сравнивает значения «low_point» и «high_point», чтобы проверить, меньше ли «low_point», чем «high_point». Мы, вероятно, будем прогрессировать, если это так. В противном случае наша сортировка остановится. Когда наша сортировка останавливается, это означает, что список отсортирован.
Затем наш код вызывает метод prepare(). Это находит указатель поворота и перемещает объекты в нужные места. Таким образом, наша программа дважды вызывает метод quicksort(). Мы впервые используем QuickSort для фрагментов слева от оси. Для второй попытки мы используем QuickSort для объектов справа от точки поворота. В результате, поскольку она вызывает сама себя, наша функция является рекурсивной. Давайте теперь создадим основную программу, которая создает сортируемый список. Начнем с указания набора значений для сортировки. Функция Python len() используется для определения длины нашего набора атрибутов. После этого применяется метод quicksort().
def prepare(data, low_point, high_point):
pivot = data[high_point]
n = low_point — 1
for i in range(low_point, high_point):
if data[i] <= pivot:
n = n + 1
(data[n], data[i]) = (data[i], data[n])
(data[n + 1], data[high_point]) = (data[high_point], data[n + 1])
return n + 1
def quick_sort(data, low_point, high_point):
if low_point<high_point:
pivot = prepare(data, low_point, high_point)
quick_sort(data, low_point, pivot — 1)
quick_sort(data, pivot + 1, high_point)
my_list = [9, 5, 1, 7, 4, 2]
total = len(my_list)
quick_sort(my_list, 0, total — 1)
print(my_list)
Здесь вы можете видеть, что данные отсортированы.
Пример 2
В этом примере мы будем использовать две функции: partition() и quicksort(). Функция quicksort() сначала разделяет коллекцию, а затем рекурсивно вызывает себя для разделенных частей. Во-первых, давайте посмотрим на функцию Division(). Сначала был установлен стержень, как вы можете видеть в коде. Если значение, которое мы сейчас просматриваем, выше точки разворота. Мы можем перейти к следующей части слева, потому что она находится справа от оси. Мы также должны убедиться, что мы не прошли нижний указатель, который указывает, что все элементы были перемещены в правильную сторону от точки поворота. После этого осуществляется способ, обратный вышеописанному. Мы либо нашли неупорядоченное число как для high_point, так и для low_point, или low_point больше, чем high_point, и в этом случае мы выходим из цикла. Наконец, давайте запустим код quicksort().
def partition(arr1, start, end):
pivot = arr1[start]
low_point = start + 1
high_point = end
while True:
while low_point= pivot:
high_point = high_point — 1
while low_point<= high_point and arr1[low_point] <= pivot:
low_point = low_point + 1
if low_point= end:
return
p_func = partition(arr1, start, end)
quick_sort(arr1, start, p_func-1)
quick_sort(arr1, p_func+1, end)
arr1 = [23,22,56,4,26,77,10,33,44,12,57,78,22,83,43,31,98,76]
quick_sort(arr1, 0, len(arr1) — 1)
print(arr1)
Это результат. Нет никакой гарантии, что эти два 22 были в таком порядке, потому что метод нестабилен. Возможно, сначала они были переключены, но это ничего не значит в целочисленном массиве.
Пример 3
В этом примере мы собираемся сортировать пользовательские объекты. Существует несколько различных способов расширения этого алгоритма для сортировки пользовательских объектов в Python. Операторы сравнения для определенного класса могут быть реализованы в стиле Pythonic, что означает, что нам не придется менять алгоритм, потому что >, ==, = и т. д. будут лучше всего работать с нашим объектом класса. Еще один вариант — заставить вызывающую сторону предоставить нашему алгоритму метод, который затем будет использоваться для выполнения фактического сравнения элементов. Довольно просто переписать алгоритм для использования с заказными объектами. Однако имейте в виду, что алгоритм не является полностью стабильным. Начнем с класса Student. Этот класс имеет только две характеристики: имя ученика и возраст. Мы будем сортировать по возрасту, чего мы добьемся, добавив в алгоритм сортировки новую лямбда-функцию. Но сначала, давайте посмотрим, как эта функция используется в алгоритме. Вместо использования операторов = или >= для прямого сравнения мы используем функцию, чтобы определить, кто из учеников старше. Lambda передает объект в сравнении с вызовом быстрой сортировки, который выполняет точное сравнение атрибутов возраста.
class Student:
def __init__(self, name_of_student, age):
self.name_of_student = name_of_student
self.age = age
def __str__(self):
return self.name_of_student
def partition(arr1, start, end, compare_func):
pivot = arr1[start]
low_point = start + 1
high_point = end
while True:
while low_point<= high_point and compare_func(arr1[high_point], pivot):
high_point = high_point — 1
while low_point<= high_point and not compare_func(arr1[low_point], pivot):
low_point = low_point + 1
if low_point= end:
return
Здесь вы можете увидеть отсортированный список имен.
Заключение
Массив подразделяется с использованием алгоритма Python QuickSort, а затем сортируется каждая запись в списке; этот метод повторно вызывает эти вложенные массивы. Мы подробно рассмотрели эту концепцию с примерами в этой статье.
