В каждой сфере есть базовые знания, которыми должен обладать специалист. Для химиков, база - это знание неорганической химии, для писателя - знание грамматики, а для программиста - базовые алгоритмы. В данной статье их будет 4: пузырьковая сортировка, сортировка вставками, сортировка слиянием и быстрая сортировка.
Статья будет полезна начинающим программистам и тем, кто хочет повторить базу
Пузырьковая сортировка
Идея пузырьковой сортировки: даётся массив чисел А, каждый элемент которого сравнивается со следующим ( A[i] ? A[i+1] ), и если следующий элемент меньше( A[i] > A[i+1]), то элементы меняются местами.
Сложность такого алгоритма О(n2) - в худшем случае (если список отсортирован по убыванию) и O(n), если список уже отсортирован и мы сделали лишь проверку.
Память О(n)
def bambl_sorted(n_list, permutation):
if permutation == 0: # проверка, была ли перестановка в прошлой итерации
return n_list
else:
permutation = 0
i = 0
for j in range(len(n_list)-1):
if n_list[i] > n_list[i+1]:
oper = n_list[i] # вводим переменную для смены двух элементов
n_list[i] = n_list[i+1]
n_list[i+1] = oper
permutation = 1
i += 1
bambl_sorted(n_list, permutation)
return n_list
n_list = list(map(int, input().split()))
print(*bambl_sorted(n_list, 1), sep=' ') # делаем красивый выводПояснение к коду:
Объявляем функцию bambl_sorted с 2 аргументами (исходный список и количество перестановок, которые можно заменить на булевы значения - True/False).
Если количество перестановок равно 0, то возращаем список (он уже отсортирован).
Иначе, объявляем, что перестановок 0 и i = 0 (индекс равен нулю).
Проходим циклом по списку и сравниваем элементы, если итерируемый элемент (A[i]) больше следующего (A[i+1]), то тогда меняем их местами и объявляем, что перестановок 0.
После окончания списка вновь вызываем функцию bambl_sorted.
Возращаем отсортированный список.
Стандартный ввод и вывод.
Сортировка вставками
Идея ставок очень похожа на пузырьковую сортировку и отдалённо напоминает бинарный_поиск, только вместо того, чтобы сравнивать элемент с последующим, он сравнивается с элементами предыдущего отсортированного подмассива до тех пор, пока не дойдет до A[i-1] >= A[i] >= A[i+1].
Сложность алгоритма O(n2)
Память O(n)
def insertion_sort(n_list):
for i in range(1, len(n_list)):
oper = n_list[i]
j = i - 1
while (j >= 0 and oper < n_list[j]):
n_list[j + 1] = n_list[j]
j = j - 1
n_list[j + 1] = oper
return n_list
n_list = list(map(int, input().split()))
print(*insertion_sort(n_list), sep=' ')Разберём основные фрагменты кода:
Объявляем функцию insertion_sort с исходным списком в аргументе.
Внутри функции проходимся циклом по всему списку.
Запустим цикл, который будет находить место каждому элементу.
Возращаем отсортированный массив и выходим из функции.
Стандартный ввод и вывод.
Сортировка слиянием
Идея сортировки слиянием: делим массив на множество подмассивов длинной от 1 до 2 элементов, сортируем, а далее собираем в итоговый массив подмассивы, попутно сортируя их.
Сложность алгоритма O(n log n)
Память O(n log n)
def menge_sort(a_list):
if len(a_list) > 2:
mid = len(a_list)// 2
b = a_list[:mid]
c = a_list[mid:]
del a_list
b_list = menge_sort(b)
b = len(b) - 1
c_list = menge_sort(c)
c = len(c) - 1
else:
mid = len(a_list)// 2
b_list = a_list[:mid]
b = len(b_list) - 1
c_list = a_list[mid:]
c = len(c_list) - 1
del a_list
i1 = 0
i2 = 0
a_list = []
while i1 <= b and i2 <= c:
if b_list[i1] > c_list[i2]:
a_list.append(c_list[i2])
i2 += 1
else:
a_list.append(b_list[i1])
i1 += 1
while i1 <= b:
a_list.append(b_list[i1])
i1 += 1
while i2 <= c:
a_list.append(c_list[i2])
i2 += 1
del b_list, c_list, b, c
return a_list
n_list = list(map(int, input().split()))
print(*menge_sort(n_list), sep=' ')Пояснение к коду:
Объявляем функцию menge_sort с массивом А в аргументе.
Делим массив на 2 подмассива до тех пор пока он больше 2.
Сортируем подмассивы (те маленькие, которые длинной меньше или равна 2).
"Сливаем" эти подмассивы в один, сортируя их.
Возращаем итоговый массив.
Быстрая сортировка
Идея быстрой сортировки: даётся массив А, берём медиану (число которое находится в середине, если массив упорядочен) из 3 чисел А[0], A[(o+n-1)/2], A[n-1] - это будет опорный элемент. Делаем 3 указателя: между подмассивом, где меньше опорного элемента и равны; подмассивом от равных до бОльших; рассматриваемый элемент. Далее, рекурсией применяем такую же операцию к подмассивам, где все элементы меньше опорного и больше, пока их длина больше 2.
Сложность алгоритма O(n log n)
Память O(n)
def median(a, b, c):
if a < b:
if a > c:
if b > c:
return b
else:
return c
else:
return a
else:
if b > c:
if a > c:
return a
else:
return c
else:
return b
def partition(n_list, beginning, end):
x = median(n_list[beginning], n_list[(beginning + end) // 2], n_list[end])
n, e, g = beginning, beginning, beginning
while end >= n:
if n_list[n] < x:
y = n_list[n]
n_list[n] = n_list[g]
n_list[g] = n_list[e]
n_list[e] = y
e += 1
g += 1
elif n_list[n] == x:
y = n_list[n]
n_list[n] = n_list[g]
n_list[g] = y
g += 1
n += 1
if e < 2:
return [0, g]
else:
return [e-1, g]
def quick_sort(n_list, beginning, end):
if (end-beginning) > 1:
separating_indexes = partition(n_list, beginning, end)
quick_sort(n_list, beginning, separating_indexes[0])
quick_sort(n_list, separating_indexes[1], end)
else:
if end > beginning:
if n_list[beginning] > n_list[end]:
n_list[beginning], n_list[end] = n_list[end], n_list[beginning]
return n_list
n_list = list(map(int, input().split()))
if len(n_list) <= 1:
print(*n_list, sep=' ')
else:
print(*quick_sort(n_list, 0, len(n_list)-1), sep=' ')Разберём основные фрагменты кода (тут разберём по функциям):
Функция Median
Тут только ищем среднее значение :)
Функция Partition с аргументами: массив, индекс начала подмассива, индекс конца подмассива:
Делаем 3 указателя: между частью, где меньше опорного элемента и равны; подмассивом от равных до бОльших; рассматриваемый элемент. Сортируем относительно опорного элемента и возращаем индексы неотсортированного.
Функция Quick_sort с аргументами: массив, индекс начала подмассива, индекс конца подмассива:
Если длина подмассива больше 1 (в одном случае может быть 2), применяем функцию Partition, далее рекурсивно вызываем Quick_sort для неотсортированных частей массива. Если длина больше или равна 1, сортируем крайние элементы. Возращаем отсортированный список.
Стандартный ввод и вывод (если длина массива не больше 1, то нет смысла сортировать).
Надеюсь статья была вам полезна.
Также для лучшего изучения алгоритмов советую прочитать А. Бхаргава "Грокаем алгоритмы" и Т. Рафгарден "Совершенный алгоритм. Основы".