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

Сортировка выборкой — известнейший алгоритм, сегментирующий список на 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(n²), где n — это число элементов списка.

Источник