Сортировка методом выбора
Доброе время суток участники образовательной IT площадки GeekSpace. Меня зовут Юрий Сиротенко и сегодня мне бы хотелось поговорить о таком алгоритме как “Сортировка методом выбора”.
Если вы хотите ознакомиться с данным материалом в видео формате, вы можете найти запись в лектории или просто перейти по ссылке. Также вы сможете получить методичку и перезентацию на данную тему под видео - лекцией.
Введение
Алгоритм сортировки методом выбора по эффективности фактически равнозначен алгоритму пузырьковой сортировки. Почему фактически? Хоть и при выполнении сравнения элементов требуется столько же шагов, что и в пузырьковой сортировки, однако количество перестановок уменьшается.
Время сравнения является определяющим фактором, поэтому, как правило, считается, что эффективность алгоритмов пузырьковая сортировка и сортировка методом выбора одинакова, но все же алгоритм сортировки методом выбора выполняется быстрее из-за меньшего количества перестановок.
Описание
Помните пример с учениками выстроенных в одну шеренгу который я приводил в лекции “Пузырьковая сортировка”? Давайте вернемся к нему.
Перебор начинается от крайнего левого учащегося шеренги. Для начала нужно записать рост крайнего левого учащегося в позиции 0 и положить около него мяч
Затем сравним рост следующего учащегося с записанным ранее. Если рост следующего по порядку учащегося меньше показателя, который был записан ранее, нужно вычеркнуть записанный ранее рост и вписать новый, а также переложить мяч рядом с учеником который ниже ростом.
Давайте продолжим обход шеренги с учащимися сравнивая рост каждого с ранее записанным. Рост учащегося в позиции 2 заметно больше записанного ранее, поэтому перемещать мяч и перезаписывать минимальный показатель роста мы не станем
Аналогично и с учащимся в позиции 3
А вот рост учащегося в позиции 4 куда меньше записанного, поэтому запишим новый минимальный рост и переместим мячик
Рост последнего учащегося в шеренги в позиции 5 заметно больше чем записанный показатель, поэтому мяч остается в своей позиции
Проход закончен. Теперь мячик лежит перед самым низкорослым учеником. Теперь необходимо поменять местами самого первого в шеренги ученика, который стоит в позиции 0 с учащимся возле которого лежит мячик, то есть в позиции 4. Делается это для того, чтобы самый низкий ученик стоял в самом начале
Готово. Теперь самый низкорослый ученик стоит в самом начале. Только что было проведено N - 1 сравнений, но только одна перестановка.
С каждым последующим проходом еще один ученик сортируется и переходит на левый край, и поиск следующего минимума производится среди меньшего количества учащихся
Реализация
Давайте рассмотрим реализацию алгоритма сортировки методом выбора при помощи языка программирования PHP
1 <?php
2
3 function sort_select(array &$arr) {
4 for ($out = 0; $out < (count($arr) - 1); $out++) {
5 $min = $out;
6
7 for ($in = $out + 1; $in < count($arr); $in++) {
8 if ($arr[$in] < $arr[$min]) {
9 $min = $in;
10 }
11 }
12
13 $tmp = $arr[$out];
14 $arr[$out] = $arr[$min];
15 $arr[$min] = $tmp;
16
17 }
18 }
Функция sort_select принимает в качестве параметра структуру данных массив по ссылке. В задачу функции входит отсортировать массив от меньшего к большему при помощи алгоритма сортировки методом выбора.
Цикл объявленный в строке 4 является внешним проходом. Число его итерация равно длине сортируемого массива - 1. Минус один, потому что последний элемент массива после полного прохода в сортировки не нуждается.
В пятой строке мы выписываем позицию каждого внешнего прохода в переменную, которая будет указывать на позицию с минимальным значением.
Затем седьмой строкой мы начинаем внутренний проход по элементам. В цикле for декларируется переменная “$in” которая равняется “$out + 1”. Плюс один потому что значение следующего элемента в позиции “$in” будет сравниваться с минимальным и если такое значение меньше чем указано в переменной “$min”, то эта самая переменная “$min” будет переписана.
После того, как внутренний проход был завершен, переменная “$min” будет указывать на позицию с минимальным значением.
В строках 13-15 производится перемещение значений.
Давайте разберем небольшую консольную программу в которой производится сортировка
1 <?php
2
3 require __DIR__ . '/select_function.php';
4
5 $arr = [9, 12, 1, 3, 19, 17, 21, 4, 2, 7,];
6
7 echo implode(',', $arr) . "\n";
8 sort_select($arr);
9 echo implode(',', $arr) . "\n";
В третьей строке была объявлена переменная “$arr”, в которую было внесено неупорядоченное множество целочисленных элементов, а в 8 строке производится сортировка
Запуск
Давайте запустим нашу программу
php sort_select.php
9,12,1,3,19,17,21,4,2,7
1,2,3,4,7,9,12,17,19,21
Как видим сортировка была выполнена успешно.
Заключение
Сортировка методом выбора, как было сказано ранее, выполняет такое же количество сравнений, что и пузырьковая сортировка:
N * (N - 1) / 2
Для каждых 10 элементов выполняются 45 сравнений, однако количество перестановок уменьшается. Поэтому можно с уверенностью сказать, что сортировка методом выбора выполняется быстрее пузырьковой сортировки из-за меньшего количества перестановок.