Сортировка выбором в Python: Подробный разбор алгоритма

Что такое сортировка выбором?

Сортировка выбором (Selection Sort) - это алгоритм сортировки, который находит минимальный элемент в неотсортированной части списка и помещает его в начало. Процесс повторяется для оставшейся части списка.

Мы рассмотрим пример задачи сортировки по возрастанию значений списка numbers из имеющихся чисел [5, 4, 9, 8, 7, 6].

Пример рабочего кода:

Выше написано правильное написание кода

Тот же код ниже для копирования и вставки в программу. Не забывайте про необходимый отступ пробелами в определённых местах в начале строки, так как код на сервере блога может отображаться некорректно.

def selection_sort(my_list):
for i_minimal in range(len(my_list)):
for current in range(i_minimal, len(my_list)):
if my_list[current] < my_list[i_minimal]:
my_list[current], my_list[i_minimal] = my_list[i_minimal], my_list[current]


numbers = [5, 4, 9, 8, 7, 6]

selection_sort(numbers)

print(numbers)

Детальный разбор кода

Построчный анализ:

1. Объявление функции: def selection_sort(my_list): # Создает функцию, принимающую список как параметр. Алгоритм сортировки символов. Объявление функции selection_sort. Аргумент функции в скобках (my_list)
   
2. Внешний цикл: for i_minimal in range(len(my_list)): # Отвечает за позицию, куда будет помещен минимальный элемент. i_minimal — переменная которая будет отвечать за номер места, куда мы будем вставлять очередное по списку минимальное число.
   
3. Внутренний цикл: for current in range(i_minimal, len(my_list)): # Перебирает оставшиеся неотсортированные элементы. Внешний цикл отвечает за сравнение всех цифр в списке. len(my_list) — Точка окончания цикла и соответствует длине нашего списка. i_minimal — начало списка будет в этой переменной, так как нам не нужно сравнивать цифры, где уже лежат отсортированные элементы списка.
   
4. Сравнение элементов: if my_list[current] < my_list[i_minimal]: # Сравнивает текущий элемент с минимальным. Попарное сравнение элементов в списке (текущего элемента и элемента, который занимает сейчас место минимального). Сравниваем первый элемент в списке со всеми остальными элементами. Затем сравниваем второй элемент в списке со всеми остальными элементами. Затем сравниваем 3, 4 и так далее. В конце сравнения минимальный занимает место в списке соответственно своему значению. То есть если символ меньше, то встает на место минимального (если это необходимо, меняется местами со сравниваемым символом).
   
5. Обмен элементов: Выполняется swap операция при нахождении меньшего элемента
6. my_list[current], my_list[i_minimal] = my_list[i_minimal], my_list[current] # Постановка минимального элемента списка в нужное нам место.
7. numbers = [5, 4, 9, 8, 7, 6] # Это предустановленный список, который будет обрабатывать наша программа
8. selection_sort(numbers) # Создаем свою функцию
9. print(numbers) # Вывод на экран отсортированного списка
   

Результат работы программы:

Области применения отсортированных списков:

• Поиск информации в базах данных
• Телефонные справочники и адресные книги
• Словари и энциклопедии
• Анализ данных и статистика
• Календарные планировщики
• Музыкальные плейлисты

Рекомендации по улучшению кода:

• Добавить документацию;
• Добавить проверку входных данных;
• Оптимизировать производительность: добавить возможность раннего выхода если список уже отсортирован. Использовать enumerate() для более читаемого кода;
• Добавить возможность сортировки по убыванию;

Сложность алгоритма:

• Временная сложность: O(n²)
• Пространственная сложность: O(1)

Заключение

Сортировка выбором - это простой, но не самый эффективный алгоритм сортировки.

Его преимущества:

• Простота реализации
• Стабильность
• Минимальное использование памяти

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

ПОЛЕЗНЫЕ РЕСУРСЫ:

---------------------------------------------------

Сообщество дизайнеров в VK

https://vk.com/grafantonkozlov

Телеграмм канал сообщества

https://t.me/grafantonkozlov

Архив эксклюзивного контента

https://boosty.to/antonkzv

Канал на Дзен

https://dzen.ru/grafantonkozlov

---------------------------------------------------

Бесплатный Хостинг и доменное имя

https://tilda.cc/?r=4159746

Мощная и надежная нейронная сеть Gerwin AI

https://t.me/GerwinPromoBot?start=referrer_3CKSERJX

GPTs — плагины и ассистенты для ChatGPT на русском языке

https://gptunnel.ru/?ref=Anton

---------------------------------------------------