Сортировка методом выбора

Доброе время суток участники образовательной 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 сравнений, однако количество перестановок уменьшается. Поэтому можно с уверенностью сказать, что сортировка методом выбора выполняется быстрее пузырьковой сортировки из-за меньшего количества перестановок.