Алгоритм сортировки выборкой с примером на Python | OTUS

Курсы

Программирование
iOS Developer. Basic
-23%
Python Developer. Professional
-13%
Разработчик на Spring Framework
-23%
Golang Developer. Professional
-17%
Python Developer. Basic
-16%
iOS Developer. Professional
-13%
Node.js Developer
-15%
Unity Game Developer. Professional
-11%
React.js Developer
-12%
Android Developer. Professional
-7%
Software Architect
-12%
C++ Developer. Professional
-8%
Разработчик C#
-8%
Backend-разработчик на PHP Архитектура и шаблоны проектирования
-12%
Программист С Базы данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Agile Project Manager Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер-практикум по использованию и настройке GIT IoT-разработчик Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-17%
DevOps практики и инструменты
-18%
Архитектор сетей
-21%
Инфраструктурная платформа на основе Kubernetes
-22%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив по управлению миграциями (DBVC)
-16%
Administrator Linux.Basic
-10%
Супер-интенсив «ELK»
-10%
Administrator Linux. Professional MS SQL Server Developer Безопасность Linux PostgreSQL Reverse-Engineering. Professional CI/CD VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Алгоритм сортировки выборкой с примером на Python

Algo_Deep_14.4-5020-efbc8a.png

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

Однако на деле вам не надо создавать новый список для сортированных элементов. В качестве него подойдёт и крайняя левая часть списка. То есть после нахождения наименьшего элемента он меняется с первым элементом местами.

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

Реализация алгоритма сортировки выборкой

На языке программирования Python алгоритм можно реализовать следующим образом:

def selection_sort(nums):  
    # Значение i отвечает числу отсортированных значений
    for i in range(len(nums)):
        # Изначально считаем наименьшим первый элемент
        lowest_value_index = i
        # Данный цикл перебирает несортированные элементы
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[lowest_value_index]:
                lowest_value_index = j
        # Наименьший элемент меняем с первым в списке
        nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i]

# Проверяем, что всё работает
random_list_of_nums = [12, 8, 3, 20, 11]  
selection_sort(random_list_of_nums)  
print(random_list_of_nums) 

Обратите внимание, что в процессе увеличения значения i надо проверять всё меньше элементов.

Время сортировки

Время сортировки в среднем составляет O(n2), где n — это число элементов списка.

Источник

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться