На этой неделе Хагрид учит нас сортировке по выбору, так что шшш! Поскольку он на самом деле не должен обучать нас какой-либо магии и не говоря уже о том, что его исключили еще до того, как он закончил Хогвартс, вполне естественно, что заклинание, которому он собирается нас научить, не так уж и эффективно. Однако у него все еще есть применение.

Сортировка выделения

Вот ваше заклинание:

Для простоты я разделил наше заклинание на две функции, поскольку одна функция просто абстрагирует незначительную деталь алгоритма - подкачку.

Функция подкачки принимает три параметра: первый - это список, второй - первое значение, которое нужно поменять местами, а третий - второе значение, которое нужно поменять местами. Он сохраняет элемент в list[first] во временной переменной перед изменением list[first] на равное list[second]. Наконец, list[second] будет равно temp, которое изначально было значением list[first] до того, как мы его изменили. temp необходим для хранения исходного значения. В противном случае вы вернете список с повторяющимися номерами.

Что касается самого заклинания, то все довольно просто.

С алгоритмами сортировки выбора у вас есть внутренний и внешний цикл. Внешний цикл начинается с нуля и устанавливает значение min. Это значение начинается с 0.

Внутренний цикл сравнивает остальную часть массива со значением list[min], которое начинается с 0. Если элемент с list[j] больше, чем list[min], мы делаем j новым min.

Наконец, мы проверяем, изменился ли min. Он изменится, если он больше не равен i. Если это так, мы вызываем функцию swap, передавая list, i и min в качестве аргументов. Затем мы повторяем цикл, отчасти поэтому этот алгоритм так неэффективен.

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

Заключение

Но вот и все: сортировка по выбору. Применение этого заклинания немного похоже на стрельбу из Флипендо в замедленной съемке, но иногда оно все же помогает. Надеюсь, вам понравилось заклинание на этой неделе, а на следующей неделе я займусь поиском в ширину (BFS). Ваше здоровье!