Реализация и анализ сортировки выбором
Всем привет! Совсем недавно мы говорили с вами про bubble sort - сортировку пузырьком. А теперь пришло время говорить о более быстрых алгоритмах, так как в прошлом посте мы выяснили, что сортировка пузырьком хоть и выполняет свою задачу, но делает это не очень эффективно. И так начнем:
Сортировка выбором — это простой алгоритм сортировки, который многократно находит минимальный элемент из несортированной части массива и помещает его в начало массива. Он работает, выбирая наименьший элемент и заменяя его элементом в текущей позиции, пока весь массив не будет отсортирован.
Вот реализация сортировки выбором в 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]
return arr
Внешний цикл проходит от 0 до n-1, где n — длина массива. На каждой итерации минимальный элемент находится из несортированной части массива (т. е. от i+1 до n-1) с помощью внутреннего цикла. Затем минимальный элемент заменяется элементом в текущей позиции (т. е. i).
Временная сложность:
Временная сложность сортировки выбором O (n ^ 2)
Надеемся вам понравился наш разбор сортировки выбором. Если у вас есть какие-то предложение, то пишите их в комментариях. Также не забудьте поставить вашу реакцию на этот пост, ведь именно это мотивирует нас делать крутой контент.
Всем отличного дня!
#learning_python_algorithms
