Введение
Алгоритмы сортировки являются важной частью программирования. В данной статье рассмотрим популярные алгоритмы сортировки в 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]Заключение
В ходе статьи мы с Вами рассмотрели популярные алгоритмы сортировки в Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂
