Youtor
Сортировка выбором Язык программирования Python
>> YOUR LINK HERE: ___ http://youtube.com/watch?v=fuwPHRPGSxg
Алгоритм сортировки выбором заключается в поиске минимального значения на необработанном срезе списка и обмене найденного минимума с первым элементом необработанного среза. На следующем шаге необработанный срез уменьшается на один элемент с начала. • Это исходный неотсортированный список. • Сначала он берется целиком и в нем находится минимальное значение. • Далее минимум записывается в первую ячейку, а значение из первой ячейки переносится туда, где был минимум. • На следующей итерации цикла первая ячейка уже исключается из области поиска. • Срез начинается со второго элемента. Найденный минимум будет записан в первую ячейку этого среза. • На третьей итерации из поиска исключаются первые два элемента, и так далее. • Количество итераций будет на одну меньше, чем длина списка, потому что когда доходим до последнего элемента, его уже не с чем менять. В конце и так окажется самое большое значение. • Если список состоит из десяти элементов, то количество итераций 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/sor... • Больше задач: https://younglinux.info/python/task • Приложение для андроид: https://play.google.com/store/apps/de... • Купить PDF-версию (100 задач): https://younglinux.info/store/store.h...
#############################
