В одной из прошлых статей я рассматривал списки в Python, а также затронул их сортировку. Теперь давайте разберем эту тему более подробно: изучим виды алгоритмов сортировки и сравним их скорость на примере сортировки чисел в порядке возрастания.
Встроенные методы сортировки в Python
Стандартный метод сортировки списка по возрастанию – sort(). Пример использования:
nums = [54, 43, 3, 11, 0] nums.sort() print(nums) # Выведет [0, 3, 11, 43, 54]
Метод sorted() создает новый отсортированный список, не изменяя исходный. Пример использования:
nums = [54, 43, 3, 11, 0] nums2 = sorted(nums) print(nums, nums2) # Выведет [54, 43, 3, 11, 0] [0, 3, 11, 43, 54]
Если нам нужна сортировка от большего числа к меньшему, то установим флаг reverse=True. Примеры:
nums = [54, 43, 3, 11, 0] nums.sort(reverse=True) print(nums) # Выведет [54, 43, 11, 3, 0] nums = [54, 43, 3, 11, 0] nums2 = sorted(nums, reverse=True) print(nums, nums2) # Выведет [54, 43, 3, 11, 0] [54, 43, 11, 3, 0]
Но будет полезно знать и другие виды сортировки, так как не всегда встроенные методы будут подходить под все ваши задачи.
Пузырьковая сортировка
Алгоритм попарно сравнивает элементы списка, меняя их местами, если это требуется. Он не так эффективен, если нам нужно сделать только один обмен в списке, так как данный алгоритм при достижении конца списка будет повторять процесс заново. Чтобы алгоритм не выполнялся бесконечно, мы вводим переменную, которая поменяет свое значение с True на False, если после запуска алгоритма список не изменился.
Сравниваются первые два элемента. Если первый элемент больше, то они меняются местами. Далее происходит все то же самое, но со следующими элементами до последней пары элементов в списке.
Пример пузырьковой сортировки:
def bubble(list_nums):
swap_bool = True
while swap_bool:
swap_bool = False
for i in range(len(list_nums) - 1):
if list_nums[i] > list_nums[i + 1]:
list_nums[i], list_nums[i + 1] = list_nums[i + 1], list_nums[i]
swap_bool = True
nums = [54, 43, 3, 11, 0]
bubble(nums)
print(nums) # Выведет [0, 3, 11, 43, 54]
Сортировка вставками
Алгоритм делит список на две части, вставляя элементы на их правильные места во вторую часть списка, убирая их из первой.
Если второй элемент больше первого, то оставляем его на своем месте. Если он меньше, то вставляем его на второе место, оставив первый элемент на первом месте. Далее перемещаем большие элементы во второй части списка вверх, пока не встретим элемент меньше первого или не дойдем до конца списка.
Пример сортировки вставками:
def insertion(list_nums):
for i in range(1, len(list_nums)):
item = list_nums[i]
i2 = i - 1
while i2 >= 0 and list_nums[i2] > item:
list_nums[i2 + 1] = list_nums[i2]
i2 -= 1
list_nums[i2 + 1] = item
nums = [54, 43, 3, 11, 0]
insertion(nums)
print(nums) # Выведет [0, 3, 11, 43, 54]
Сортировка выборкой
Как и сортировка вставками, этот алгоритм в Python делит список на две части: основную и отсортированную. Наименьший элемент удаляется из основной части и переходит в отсортированную.
Саму отсортированную часть можно и не создавать, обычно используют крайнюю часть списка. И когда находится наименьший элемент списка, то переносим его на первое место, вставляя первый элемент на прошлое порядковое место наименьшего. Далее делаем все то же самое, но со следующим элементом, пока не достигнем конца списка.
Пример сортировки выборкой:
def selection(sort_nums):
for i in range(len(sort_nums)):
index = i
for j in range(i + 1, len(sort_nums)):
if sort_nums[j] < sort_nums[index]:
index = j
sort_nums[i], sort_nums[index] = sort_nums[index], sort_nums[i]
nums = [54, 43, 3, 11, 0]
selection(nums)
print(nums) # Выведет [0, 3, 11, 43, 54]
Пирамидальная сортировка
Этот алгоритм, как и сортировки вставками или выборкой, делит список на две части. Алгоритм преобразует вторую часть списка в бинарное дерево для эффективного определения самого большого элемента.
Преобразуем список в бинарное дерево, где самый большой элемент является вершиной дерева, и помещаем этот элемент в конец списка. После перестраиваем дерево и помещаем новый наибольший элемент перед последним элементом в списке. Повторяем этот алгоритм, пока все вершины дерева не будут удалены.
Хоть алгоритм и кажется сложным, он значительно быстрее остальных, что особенно заметно при обработке больших списков.
Пример пирамидальной сортировки:
def heapify(sort_nums, heap_size, root):
l = root
left = (2 * root) + 1
right = (2 * root) + 2
if left < heap_size and sort_nums[left] > sort_nums[l]:
l = left
if right < heap_size and sort_nums[right] > sort_nums[l]:
l = right
if l != root:
sort_nums[root], sort_nums[l] = sort_nums[l], sort_nums[root]
heapify(sort_nums, heap_size, l)
def heap(sort_nums):
size = len(sort_nums)
for i in range(size, -1, -1):
heapify(sort_nums, size, i)
for i in range(size - 1, 0, -1):
sort_nums[i], sort_nums[0] = sort_nums[0], sort_nums[i]
heapify(sort_nums, i, 0)
nums = [54, 43, 3, 11, 0]
heap(nums)
print(nums) # Выведет [0, 3, 11, 43, 54]
Сортировка слиянием
Алгоритм разделяет список на две части, каждую из них он разделяет еще на две и так далее, пока не останутся отдельные единичные элементы. Далее соседние элементы сортируются парами. Затем эти пары объединяются и сортируются с другими парами, пока не обработаются все элементы в списке.
Пример сортировки слиянием:
def mergeSort(sort_nums):
if len(sort_nums)>1:
mid = len(sort_nums)//2
lefthalf = sort_nums[:mid]
righthalf = sort_nums[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i<len(lefthalf) and j<len(righthalf):
if lefthalf[i]<righthalf[j]:
sort_nums[k]=lefthalf[i]
i=i+1
else:
sort_nums[k]=righthalf[j]
j=j+1
k=k+1
while i<len(lefthalf):
sort_nums[k]=lefthalf[i]
i=i+1
k=k+1
while j<len(righthalf):
sort_nums[k]=righthalf[j]
j=j+1
k=k+1
nums = [54, 43, 3, 11, 0]
mergeSort(nums)
print(nums) # Выведет [0, 3, 11, 43, 54]
Быстрая сортировка в Python
Один из самых популярных алгоритмов при сортировке списков. При правильном использовании он не требует много памяти и выполняется очень быстро.
Алгоритм разделяет список на две равные части, принимая псевдослучайный элемент и используя его в качестве опоры, то есть центра деления. Элементы, меньшие, чем опора, перемещаются влево от опоры, а элементы, размер которых больше опоры – вправо. Этот процесс повторяется для списка слева от опоры, а также для массива элементов справа от опоры, пока весь массив не будет отсортирован. Алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементу списка.
Пример быстрой сортировки:
def partition(sort_nums, begin, end):
part = begin
for i in range(begin+1, end+1):
if sort_nums[i] <= sort_nums[begin]:
part += 1
sort_nums[i], sort_nums[part] = sort_nums[part], sort_nums[i]
sort_nums[part], sort_nums[begin] = sort_nums[begin], sort_nums[part]
return part
def quick_sort(sort_nums, begin=0, end=None):
if end is None:
end = len(sort_nums) - 1
def quick(sort_nums, begin, end):
if begin >= end:
return
part = partition(sort_nums, begin, end)
quick(sort_nums, begin, part-1)
quick(sort_nums, part+1, end)
return quick(sort_nums, begin, end)
nums = [54, 43, 3, 11, 0]
quick_sort(nums)
print(nums) # Выведет [0, 3, 11, 43, 54]
Скорость работы алгоритмов
Сортировка слиянием почти в два раза медленнее, чем быстрая сортировка. Сортировка выборкой выполняет больше сравнений, чем сортировка вставками, но выполняется немного быстрее.
Пузырьковая сортировка не подойдет для практического применения, так как она является самой медленной из всех. Но знать данный алгоритм будет полезно тем, кто хочет полностью изучить тему алгоритмов сортировки списков в Python.
Итог
Мы изучили виды сортировки списков в Python и сравнили их эффективность, а также рассмотрели встроенные методы. Надеюсь, данная статья была полезна для вас!
Комментарии