В данной статье хочу рассмотреть примеры сортировки массива, такие как пузырьковая сортировка, быстрая сортировка, сортировка слиянием.
Зачем нам нужна сортировка? Чтобы в дальнейшем было проще искать данные в массиве.
Хотя встроенная функция для сортировки sort() работает быстрее нижеперечисленных, и в большинстве случаев вы будете пользоваться ей, но знать эти алгоритмы необходимо. Почему?
- Это любят спрашивать на собеседованиях 😀 ;
- Эти алгоритмы могут быть использованы вами для сортировки двух взаимосвязанных списков данных. Например вам нужно отсортировать оценки студентов, которые хранятся в одном массиве, а в другом в том же порядке хранятся фамилии студентов. И вам нужно будет сортировать их взаимосвязано.
Итак, приступим.
Cортировка пузырьком (Bubble Sort)
Временная сложность: O(n**2), т.е. массив размером 1000 элементов будет отсортирован за 1 миллион операций (1с).
Описание:
В массиве сравниваются каждый элемент со следующим. Если элемент с меньшим индексом больше по значению, то они меняются местами. Сначала всплывает самое большое число, затем второе по величине и т.д.
a = [3, 7, 1, 4, 9, 2, 0, 6, 4]
def sort(a):
n = len(a) - 1 # Количество индексов в массиве
for i in range(n):
for j in range(n-i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
return a
print(sort(a))[0, 1, 2, 3, 4, 4, 6, 7, 9]
Быстрая сортировка (Quick Sort)
Временная сложность: O(n*log по основанию n), т.е. массив размером 1000 элементов, будет отсортирован за 10 тыс. операций (0,01с), но может достигать квадратичной, если выбран наименьший или наибольший элемент в качестве опорного.
Описание:
Берется рандомное значение pivot c помощью сhoice, далее поочередно сравниваем с ним остальные элементы, получая 3 массива: больше pivot, меньше него и равный ему. Для массивов меньше и больше вызываем рекурсивно ту же функцию, пока длина массива больше единицы. Соединяем массивы.
import random
b = [3, 7, 1, 4, 9, 2, 0, 6, 4]
def qSort(a):
if len(a) > 1:
pivot = random.choice(a)
left = [elem for elem in a if elem < pivot]
mid = [elem for elem in a if elem == pivot]
right = [elem for elem in a if elem > pivot]
return qSort(left) + mid + qSort(right)
else:
return a
print(qSort(b))[0, 1, 2, 3, 4, 4, 6, 7, 9]
Cортировка слиянием (Merge Sort)
Временная сложность: O(n*log по основанию n), т.е. массив размером 1000 элементов, будет отсортирован за 10 тыс. операций (0,01с).
Описание:
Берется массив, делится пополам рекурсивно до разделения поэлементно, затем происходит попарное сравнение элементов в этих массивах по очереди: первый из первого с первым из второго и т.д. Меньший из пары добавляется к новому массиву, и т.д. Далее это происходит рекурсивно до полной сортировки.
c = [3, 7, 1, 4, 9, 2, 0, 6, 4]
def merge(a, b): # Cлияние массивов
result = []
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] < b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
result += a[i:] + b[j:]
return result
def mergeSort(a): # Разделение массива
if len(a) > 1:
return merge((mergeSort(a[:len(a) // 2])), (mergeSort(a[len(a) // 2:])))
else:
return a
print(mergeSort(c))[0, 1, 2, 3, 4, 4, 6, 7, 9]
Надеюсь кому-нибудь это будет полезно, мне лично было очень интересно 🙂 В следующей статье я хочу разобрать алгоритмы поиска в отсортированных массивах.