Сортировка выбором. Язык программирования Python

Алгоритм сортировки выбором заключается в поиске минимального значения на необработанном срезе списка и обмене найденного минимума с первым элементом необработанного среза. На следующем шаге необработанный срез уменьшается на один элемент с начала. Это исходный неотсортированный список. Сначала он берется целиком и в нем находится минимальное значение. Далее минимум записывается в первую ячейку, а значение из первой ячейки переносится туда, где был минимум. На следующей итерации цикла первая ячейка уже исключается из области поиска. Срез начинается со второго элемента. Найденный минимум будет записан в первую ячейку этого среза. На третьей итерации из поиска исключаются первые два элемента, и так далее. Количество итераций будет на одну меньше, чем длина списка, потому что когда доходим до последнего элемента, его уже не с чем менять. В конце и так окажется самое большое значение. Если список состоит из десяти элементов, то количество итераций 9. Поскольку индексация ячеек начинается с нуля, то индекс последней также 9. Но количество элементов 10. Теперь напишем программу. Воспользовавшись функцией randint из модуля random, заполним список десятью случайными числами от -15 до 15. Если вам не знакомо выражение-генератор списка, это примерно то же самое, что заполнять список через цикл. Обратите внимание, тело цикла выполнится десять раз, то есть количество итераций будет десять. А вот значение переменной i будет меняться от нуля до девяти включительно. Такие значения сгенерирует функция range. Но количество значений будет десять, потому что у нас есть ноль. Итак, начнем писать цикл сортировки выбором. Как было сказано ранее, нам нужно девять итераций цикла. На одну меньше, чем количество элементов в списке. Если range(N) дает десять значений, значит отсюда надо вычесть 1. При этом i будет меняться от 0 до 8 включительно. Это очень удобно, потому что мы можем использовать i не только как счетчик итераций цикла, но и в качестве индекса первой ячейки необработанного среза. И эта первая ячейка на каждой итерации будет меняться. И в нее мы будем записывать минимум. В Питоне есть функция min, которая ищет минимум. Но в Питоне есть и функция сортировки. Однако мы не решаем практическую задачу, а изучаем алгоритм. Поэтому код поиска минимума напишем сами. Для поиска минимума нам надо перебрать элементы, начиная с i и заканчивая последним. То есть их индексы будут в пределах от i до N, не включая N. На каждой итерации внутреннего цикла эти индексы будем присваивать переменной j. Если ячейка с индексом i, то есть первая ячейка текущего среза, содержит значение, которое больше, чем в ячейке j, то значения надо обменять. Здесь в позицию i будет записано значение из j, а в j из i. Все работает, но это не совсем тот алгоритм, который мы описывали. Здесь за одну итерацию внешнего цикла мы делаем множество обменов, потому что это выражение может быть истинным не один раз, и несколько раз ячейка i будет перезаписываться. Нам же надо, чтобы сначала был найден минимум. И только после этого произошел только один обмен. В этом случае нам понадобится переменная, в которой будем хранить индекс ячейки найденного минимума. Сначала предполагаем, что минимум уже находится в первой ячейке среза. В цикле мы сравниваем элемент не из ячейки i, а из ячейки m. Потому что в ней находится предполагаемый минимум. И если выражение истинно, запоминаем в m, где находится минимум, его индекс, то есть текущее значение j. Обмен будет происходить только одни раз – в конце внешнего цикла. И здесь индекс ячейки, в которой находится минимум, связан с переменной m. Здесь можно прибавить единицу, потому что i мы уже как бы учли и сравнивать начинаем со следующего за i элемента. Это пример сортировки выбором с помощью цикла while. Текстовое описание решения задачи и исходный код программы: https://younglinux.info/algorithm/sort_min Больше задач: https://younglinux.info/python/task Приложение для андроид: https://play.google.com/store/apps/details?id=info.younglinux.pythonexercises Купить PDF-версию (100 задач): https://younglinux.info/store/store.html#!digiseller/detail/2882070