Сортировка выбором на Python

Введение

В данной статье познакомимся с сортировкой выбором, и реализуем её на Python.

Алгоритм работы сортировки выбором

Допустим у нас есть следующий список: [5, 7, 2, 10, 1, 8]

1. Сначала нужно найти наименьшее значение в заданном списке. В нашем случае это элемент 1;
2. Поменять местами самый первый элемент списка и самый наименьший. В итоге мы получим такой список: [1, 7, 2, 10, 5, 8];
3. Найти следующий наименьший элемент исключив из поиска самый первый элемент. У нас это 2;
4. Поменять местами второй элемент списка и найденный элемент. Получим [1, 2, 7, 10, 5, 8];
5. Проделывать все те же действия, пока не будет отсортирован весь список.

Как менялся наш список по итерациям:

1 итерация — [1, 7, 2, 10, 5, 8]

2 итерация — [1, 2, 7, 10, 5, 8]

3 итерация — [1, 2, 5, 10, 7, 8]

4 итерация — [1, 2, 5, 7, 10, 8]

5 итерация — [1, 2, 5, 7, 8, 10]

6 итерация — [1, 2, 5, 7, 8, 10]

Сортировка выбором на Python используя цикл while

Для начала сгенерируем неупорядоченный список неповторяющихся элементов и выведем его в консоль:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

Создадим переменную N, в которую сохраним длину нашего списка:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

N = len(my_lst)

Также создадим переменную i, в которой будет храниться индекс ячейки, в которую запишется следующий минимальный элемент:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

N = len(my_lst)
i = 0

Создадим цикл while, который не закончится пока не пройдётся по всем элементам списка my_lst:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

N = len(my_lst)
i = 0

while i < N - 1:

Теперь нам нужно найти минимальный элемент списка как было показано в алгоритме работы сортировки выбором. Создадим переменную m, в которой будет храниться индекс ячейки минимального элемента. Изначально приравниваем её к i, предполагая что там находится минимальный элемент:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

N = len(my_lst)
i = 0

while i < N - 1:
    m = i

Создадим переменную j, которая понадобится для поиска минимального элемента. Она будет равна ячейке идущей после i:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

N = len(my_lst)
i = 0

while i < N - 1:
    m = i
    j = i + 1

Создадим вложенный цикл while, в котором пройдёмся по списку. Внутри цикла сравним значение ячейки j и значение в m:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

N = len(my_lst)
i = 0

while i < N - 1:
    m = i
    j = i + 1

    while j < N:
        if my_lst[j] < my_lst[m]:

Если же по индексу j хранится значение меньше, чем по индексу m, то сохраняем в m индекс найдённого на данный момент минимального элемента:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

N = len(my_lst)
i = 0

while i < N - 1:
    m = i
    j = i + 1

    while j < N:
        if my_lst[j] < my_lst[m]:
            m = j

После условия добавим j += 1 для перехода к следующей ячейке:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

N = len(my_lst)
i = 0

while i < N - 1:
    m = i
    j = i + 1

    while j < N:
        if my_lst[j] < my_lst[m]:
            m = j
        j += 1

После вложенного цикла запишем в ячейку с индексом i найденный минимальный элемент, а бывшее значение по индексу i передадим m. В конце выведем отсортированный список:

from random import sample

my_lst = sample(range(10), 5)
print(my_lst)

N = len(my_lst)
i = 0

while i < N - 1:
    m = i
    j = i + 1

    while j < N:
        if my_lst[j] < my_lst[m]:
            m = j
        j += 1

    my_lst[i], my_lst[m] = my_lst[m], my_lst[i]
    i += 1

print(my_lst)

Вывод:

[4, 9, 7, 6, 0]
[0, 4, 6, 7, 9]

Сортировка выбором на Python используя цикл for

Для сортировки выбором также можно использовать цикл for. Для начала как и в предыдущем способе сгенерируем несортированный список, выведем его в консоль, и сохраним его длину в переменную N:

from random import sample

my_lst = sample(range(10), 5)
N = len(my_lst)

print(my_lst)

Создадим цикл for, в котором пройдёмся по длине списка my_lst — 1. Внутри цикла для начала создадим переменную m, в которой будет храниться индекс ячейки минимального элемента:

from random import sample

my_lst = sample(range(10), 5)
N = len(my_lst)

print(my_lst)

for i in range(N - 1):
    m = i

Теперь создадим вложенный цикл, в котором пройдёмся по индексам от i + 1, до N:

from random import sample

my_lst = sample(range(10), 5)
N = len(my_lst)

print(my_lst)

for i in range(N - 1):
    m = i

    for j in range(i + 1, N):

Во вложенном цикле добавим условие, что если по индексу j хранится значение меньше, чем по индексу m, то сохраняем в m индекс найдённого на данный момент минимального элемента:

from random import sample

my_lst = sample(range(10), 5)
N = len(my_lst)

print(my_lst)

for i in range(N - 1):
    m = i

    for j in range(i + 1, N):
        if my_lst[j] < my_lst[m]:
            m = j

После вложенного цикла поменяем местами значение по индексу i со значением по индексу m:

from random import sample

my_lst = sample(range(10), 5)
N = len(my_lst)

print(my_lst)

for i in range(N - 1):
    m = i

    for j in range(i + 1, N):
        if my_lst[j] < my_lst[m]:
            m = j
    my_lst[i], my_lst[m] = my_lst[m], my_lst[i]

После основного цикла выведем итоговый результат:

from random import sample

my_lst = sample(range(10), 5)
N = len(my_lst)

print(my_lst)

for i in range(N - 1):
    m = i

    for j in range(i + 1, N):
        if my_lst[j] < my_lst[m]:
            m = j
    my_lst[i], my_lst[m] = my_lst[m], my_lst[i]

print(my_lst)

Вывод:

[6, 1, 0, 9, 7]
[0, 1, 6, 7, 9]

Заключение

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