Привет! В этом посте мы разберём популярные алгоритмы сортировки на примере языка Python.
1. Сортировка "Пузырьком"
Название алгоритма говорит само за себя. Алгоритм сравнивает по парам элементы массива ("пузырьки"), пока самые лёгкие не "всплывут" вверх.
Вот пример функции:
def bubble_sort(a):
for i in range(len(a)-1):
for j in range(len(a)-i-1):
if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j]
return a
Такой метод сортировки самый простой, но и самый неоптимальный. При самом худшем раскладе трудоёмкость составит a².
2. Сортировка выбором
Этот алгоритм чуть сложнее предыдущего. Мы разбиваем массив на 2 подмассива: отсортированный и нет. Сначала находим максимум в исходном массиве и меняем его местами с первым элементом массива. Потом мы берём массив без учёта первого элемента и там аналогично минимум ставим на первое место и тд.
Вот пример реализации алгоритма:
def selection_sort(a):
for i in range(0, len(a) - 1):
smallest = i
for j in range(i + 1, len(a)):
if a[j] < a[smallest]:
smallest = j
a[i], a[smallest] = a[smallest], a[i]
return a
3. Сортировка вставками
Алгоритм легче двух предыдущих. На каждой итерации программа берет один из элементов и подыскивает для него место в уже отсортированном списке. Так происходит до тех пор, пока не останется ни одного неиспользованного элемента. Кстати именно так большинство людей тасует карты в играх.
def insertion_sort(arr):
for i in range(len(arr)):
cursor = arr[i]
pos = i
while pos > 0 and arr[pos - 1] > cursor:
arr[pos] = arr[pos - 1]
pos = pos - 1
arr[pos] = cursor
return arr
Понравился контент? Смотри больше в моём телеграм-канале
https://t.me/newscaleprog