Введение
В данной статье познакомимся с сортировкой выбором, и реализуем её на Python.
Алгоритм работы сортировки выбором
Допустим у нас есть следующий список: [5, 7, 2, 10, 1, 8]
- Сначала нужно найти наименьшее значение в заданном списке. В нашем случае это элемент 1;
- Поменять местами самый первый элемент списка и самый наименьший. В итоге мы получим такой список: [1, 7, 2, 10, 5, 8];
- Найти следующий наименьший элемент исключив из поиска самый первый элемент. У нас это 2;
- Поменять местами второй элемент списка и найденный элемент. Получим [1, 2, 7, 10, 5, 8];
- Проделывать все те же действия, пока не будет отсортирован весь список.
Как менялся наш список по итерациям:
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. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂
Мой Telegram канал
Мой YouTube канал
