1426 подписчиков

Алгоритмы сортировки в Python

9 сентября 20239 сен 2023

147

5 мин

Оглавление

Введение
Сортировка пузырьком
Сортировка выбором

Введение

Алгоритмы сортировки являются важной частью программирования. В данной статье рассмотрим популярные алгоритмы сортировки в Python.

Сортировка пузырьком

Сортировка пузырьком — это один из самых простых алгоритмов сортировки. Он проходит по списку несколько раз, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Процесс повторяется до тех пор, пока список полностью не отсортируется.

Сортировка пузырьком включает следующие шаги:

Алгоритм начинает сравнивать первый и второй элементы. Если первый элемент больше второго, они меняются местами.
Алгоритм продолжает сравнивать соседние элементы и менять их местами, пока весь список не будет пройден без необходимости в обмене.
Шаги 1 и 2 повторяются для каждого элемента списка до тех пор, пока весь список не будет отсортирован.

Пример сортировки пузырьком в Python:

def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]

numbers = [3, 1, 5, 2, 4]
bubble_sort(numbers)
print(numbers) # Вывод: [1, 2, 3, 4, 5]

Сортировка выбором

Данный алгоритм проходит по списку и находит наименьший элемент, затем меняет его местами с первым элементом. Далее алгоритм находит следующий наименьший элемент и меняет его местами со вторым элементом, и так далее. Процесс повторяется до тех пор, пока список полностью не отсортируется.

Сортировка выбором включает следующие шаги:

Алгоритм начинает с первого элемента и проходит по списку, чтобы найти минимальный элемент.
Минимальный элемент меняется местами с первым элементом неотсортированной части списка.
Шаги 1 и 2 повторяются для оставшейся части списка, начиная со второго элемента. Таким образом, каждая итерация сортирует один элемент.

Пример сортировки выбором в Python:

def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]

numbers = [3, 1, 5, 2, 4]
selection_sort(numbers)
print(numbers) # Вывод: [1, 2, 3, 4, 5]

Сортировка вставками

Алгоритм сортировки вставками строит отсортированную часть списка, постепенно вставляя каждый элемент на свое место. Он начинает с первого элемента и перемещается вправо, сравнивая каждый элемент с предыдущими элементами и вставляя его на правильное место.

Сортировка вставками включает следующие шаги:

Алгоритм начинается со второго элемента и проходит по списку.
Каждый элемент сравнивается с предыдущими элементами в отсортированной части списка. Если текущий элемент меньше предыдущего элемента, то они меняются местами. Этот процесс повторяется до тех пор, пока текущий элемент не будет находиться на своем правильном месте.
Шаги 1 и 2 повторяются для всех элементов списка.

Пример сортировки вставками в Python:

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

numbers = [3, 1, 5, 2, 4]
insertion_sort(numbers)
print(numbers) # Вывод: [1, 2, 3, 4, 5]

Сортировка слиянием

Алгоритм сортировки слиянием разделяет список на две половины, рекурсивно сортирует каждую половину, а затем объединяет их в отсортированный список.

Сортировка слиянием включает следующие шаги:

Исходный список рекурсивно разделяется пополам, пока он не будет содержать только один элемент.
Каждый подсписок сортируется отдельно с помощью сортировки слиянием.
Отсортированные подсписки объединяются в один отсортированный список. При слиянии элементы сравниваются и помещаются в новый список в правильном порядке.

Пример сортировки слиянием в Python:

def merge_sort(nums):
if len(nums) > 1:
mid = len(nums)//2
left = nums[:mid]
right = nums[mid:]
merge_sort(left)
merge_sort(right)

i = j = k = 0

while i < len(left) and j < len(right):
if left[i] < right[j]:
nums[k] = left[i]
i+=1
else:
nums[k] = right[j]
j+=1
k+=1

while i < len(left):
nums[k] = left[i]
i+=1
k+=1

while j < len(right):
nums[k] = right[j]
j+=1
k+=1

numbers = [3, 1, 5, 2, 4]
merge_sort(numbers)
print(numbers) # Вывод: [1, 2, 3, 4, 5]

Быстрая сортировка

Данный алгоритм выбирает опорный элемент из списка и разделяет список на две части: одну с элементами, меньшими опорного, и другую с элементами, большими опорного. Затем алгоритм рекурсивно применяется к обеим частям.

Быстрая сортировка включает следующие шаги:

Из исходного списка выбирается опорный элемент. Этот элемент будет сравниваться со всеми остальными элементами списка.
Исходный список разделяется на две части: элементы, меньшие или равные опорному, и элементы, большие опорного.
Оба подсписка, полученные после разделения, рекурсивно сортируются с помощью быстрой сортировки.
После сортировки подсписков, элементы объединяются в один отсортированный список.

Пример быстрой сортировки в Python:

def quick_sort(arr):
if len(arr) <= 1:
return arr

pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)

numbers = [3, 1, 5, 2, 4]
sorted_numbers = quick_sort(numbers)
print(sorted_numbers) # Вывод: [1, 2, 3, 4, 5]

Пирамидальная сортировка

Данный алгоритм строит кучу из исходного списка, затем постепенно извлекает наибольший элемент из кучи и помещает его в конец списка.

Пирамидальная сортировка включает следующие шаги:

Изначально, исходный список преобразуется в кучу. Куча представляет собой бинарное дерево, где каждый узел имеет значение, меньшее или равное значению его дочерних узлов.
После построения кучи, наибольший элемент (корень кучи) вынимается и помещается в конец списка. Затем происходит восстановление свойств кучи для оставшихся элементов. Этот шаг повторяется до тех пор, пока вся куча не будет отсортирована.

Пример пирамидальной сортировки в Python:

def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2

if left < n and arr[i] < arr[left]:
largest = left

if right < n and arr[largest] < arr[right]:
largest = right

if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)

def heap_sort(arr):
n = len(arr)

# Построение кучи
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)

# Извлечение элементов из кучи
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)

return arr

numbers = [3, 1, 5, 2, 4]
sorted_numbers = heap_sort(numbers)
print(sorted_numbers) # Вывод: [1, 2, 3, 4, 5]