Мы все виноваты в этом. Когда мы сталкиваемся с проблемой, требующей отсортировать массив, мы по умолчанию используем пузырьковую сортировку. Я знаю, что мы можем добиться большего!
В качестве быстрого освежения мы предлагаем вам таблицу различных алгоритмов сортировки и их нотацию с большой буквой O.
Как мы видим, в среднем временная сложность быстрой сортировки равна n log от n, а в худшем случае сложность равна n в квадрате.
Если мы посетим каждый элемент только один раз, то у нас будет O (N).
У нас есть O (N²), когда для каждого элемента мы посещаем каждый другой элемент. Например, в случае пузырьковой сортировки каждый раз, когда мы добавляем новый элемент в список, мы должны не только сравнивать его с каждым элементом, но также сравнивать каждый элемент с ним.
Каждый раз, когда вы видите Log₂N, вы должны автоматически думать о подмножестве N элементов в списке. В алгоритме быстрой сортировки мы посещаем каждый элемент один раз. По этой причине перед журналом стоит буква N. Учитывая, что в среднем у нас примерно одинаковое количество элементов, которые больше или меньше, чем точка поворота, нам требуется проходить все меньше и меньше элементов, чтобы отсортировать список, поскольку мы продолжаем разбивать на основе текущей точки поворота. . По этой причине быстрая сортировка имеет временную сложность O (NLog₂N).
Пузырьковая сортировка
Предположим, у нас есть следующий список.
Начнем со сравнения первого элемента со следующим.
Поскольку второй элемент меньше первого, мы меняем их местами.
Затем мы перемещаем указатель на второй элемент и сравниваем его с третьим.
Поскольку третий элемент больше текущего, мы просто идем дальше.
9 больше 3. Поэтому мы их меняем местами.
Перемещаем указатель.
9 больше 8. Таким образом, мы их меняем местами.
Мы повторяем этот процесс, пока не пройдемся по всем индексам в списке.
Как мы видим, с помощью пузырьковой сортировки после первого прохода мы можем гарантировать только то, что первый элемент находится в правильном положении. Поэтому повторяем процесс, начиная со следующего индекса.
Быстрая сортировка
Предположим, у нас есть тот же список, что и в предыдущем примере.
Мы начинаем с выбора одного числа в качестве точки поворота. Поворотом может быть что угодно, но в этом примере мы выбираем последний элемент в списке.
Сравнение чисел в списке будет относиться к опорной точке. Другими словами, все числа выше, чем наша точка поворота, будут помещены в один список, а все числа ниже нашей точки поворота будут помещены в другой список.
4 больше 2. Таким образом, он помещается в список справа.
Повторяем процесс для остальных элементов.
После первого прохода мы можем гарантировать, что точка поворота находится в правильной позиции отсортированного списка. Затем процесс повторяется для каждого из двух только что созданных списков.
Поскольку в списке слева только один элемент, он уже отсортирован.
Мы используем последний элемент в списке как точку опоры.
Мы помещаем все числа больше 6 в один список и все числа меньше 6 в другой.
Перебираем оставшиеся списки.
Завершаем отсортированным списком.
Пример Python
Для начала мы создаем список из 1000 элементов от 0 до 100.
import random
number_of_elements = 1000
max_element_value = 100
min_element_value = 0
elements = []
for i in range(number_of_elements):
number = random.randint(min_element_value, max_element_value)
elements.append(number)
Мы определяем функцию для сортировки списка, используя алгоритм пузырьковой сортировки в качестве основы для сравнения.
def bubble_sort(elements):
for i in range(len(elements)):
for j in range(len(elements) - 1):
if elements[j] > elements[j+1]:
temp = elements[j]
elements[j] = elements[j+1]
elements[j+1] = temp
return elements
Мы сортируем список и получаем приблизительную оценку того, сколько времени это займет.
import time
start_time = time.time()
sorted_elements = bubble_sort(elements)
print("--- %s seconds ---" % (time.time() - start_time))
--- 0.09066176414489746 seconds ---
Мы можем подтвердить, что мы действительно отсортировали массив, просмотрев первый и последний элементы.
print(sorted_elements[:10]) print(sorted_elements[-10:]) [0, 0, 0, 0, 0, 0, 0, 1, 1, 1] [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
Реализуем алгоритм быстрой сортировки с использованием рекурсии.
def quick_sort(elements):
if len(elements) <= 1:
return elements
pivot = elements.pop()
greater_than_elements = []
lesser_or_equal_than_elements = []
for element in elements:
if (element > pivot):
greater_than_elements.append(element)
else:
lesser_or_equal_than_elements.append(element)
return quick_sort(lesser_or_equal_than_elements) + [pivot] + quick_sort(greater_than_elements)
Наконец, мы сортируем список.
import time
start_time = time.time()
sorted_elements = quick_sort(elements)
print("--- %s seconds ---" % (time.time() - start_time))
--- 0.03184390068054199 seconds ---
Как мы видим, при сортировке массива из 1000 элементов у нас уже есть заметная разница во времени, затрачиваемом на пузырьковую сортировку и быструю сортировку. На первое уходит примерно треть времени на первое!
