Видео: Сортировка выбором - разбор алгоритма для интервью

Всем привет! Меня зовут Александр Вагнер. В данном посте хочу рассмотреть такой алгоритм сортировки, как "Сортировка выбором". Суть данного алгоритма заключается в том, что на каждой итерации, начиная с первого элемента, мы находим минимальный элемент и меняем его местами сначала с первым элементом, потом, начиная со второго элемента снова ищем минимальный элемент, и меняем его местами со вторым. Потом начиная с третьего элемента снова ищем минимальный и так до тех пор, пока массив не станет отсортированным.

Например, рассмотрим задачу: дан массив из неотсортированных чисел, и на выходе нужно получить отсортированный массив.

Дано: [5, 3, 6, 2, 10, 7]

Берем первый элемент 5, и среди оставшихся 3, 6, 2, 10, 7 ищем минимальный, это 2. Затем меняем 5 и 2 местами. Получим следующий массив:

[2, 3, 6, 5, 10, 7]

Затем, начиная со второго элемента 3 ищем среди оставшихся 6, 5, 10, 7 число меньшее 3, но такого элемента нет, поэтому переходим к следующему числу 6 и среди оставшихся 5, 10, 7 ищем число, меньше чем 6, это 5. И меняем 6 и 5 местами. Получаем следующий массив:

[2, 3, 5, 6, 10, 7]

Снова переходим к следующему элементу, это теперь 6 и среди оставшихся 10, 7 ищем число меньшее 6. Но такого числа нет, поэтому переходим к 10 и остается одно число это 7, а 7 меньше 10, поэтому меняем их местами и получаем полностью отсортированный массив:

[2, 3, 5, 6, 7, 10

Код из видео:

def selection_sort(arr: list) -> list:
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Материал подготовлен с ❤️ редакцией Кухни IT.