Пузырьковая сортировка

Пузырьковую сортировку нельзя назвать эффективным алгоритмом, но это именно тот алгоритм, с которого стоит начать изучение других видов сортировки

Если вы хотите ознакомиться с данным материалом в видео формате, вы можете найти запись в лектории или просто перейти по ссылке. Также вы сможете получить методичку и перезентацию на данную тему под видео - лекцией.

О структуре данных массив я уже рассказывал в предыдущих конспектах. Также в рамках данного цикла конспектов я рассказывал о таких алгоритмах как "Линейный" и "Бинарный" поиск.

Когда в вашем хранилище накопится большой объем данных, неизбежно возникает необходимость в сортировки этих данных по какому - либо критерию. Имена потребуется отсортировать по алфавиту, рабочих кадров по дате найма, учащихся по среднему баллу и т.д.

how-to-sort-in-excel_320x240.jpg

Сортировка данных также может стать необходимым подготовительным шагом перед поиском. Например я уже говорил в одной из предыдущих лекций, что алгоритм “двоичный поиск” выполняется намного быстрее линейного поиска, но он применяется только для упорядоченных структур. Упорядочить структуру можно как раз таки при помощи алгоритмов сортировки.

Наверняка каждый слушатель помнит школьные годы, когда на уроках физической культуры преподаватель просил построится в шеренгу по росту. Лично я был почти в самом начале этой шеренге, ибо мой рост нельзя назвать маленьким, но речь не обо мне. Нам было довольно просто понять кто выше, а кто ниже. Сравнение происходило визуально на глаз и споров практически не возникало. Компьютерной программе сделать похожее действие не так просто, но вполне возможно

Представим что мы на уроке физической культуры. Учащиеся выстроились в одну линию но не по росту, а совершенно хаотично. Преподаватель попросил вас помочь выстроить учеников по росту. Академически говоря ваша задача отсортировать учащихся по единственному критерию - рост.

6456.eps_320x240.png

Для вас нет никакой сложности выстроить учащихся в нужно порядке. Но попытайтесь представить себя на месте компьютерной программы. Каким образом она может справиться с поставленной задачей?

Давайте пронумеруем позиции учащихся

6456.eps_2_320x240.png

Вы подходите к левому краю шеренги (позиция 0) и сравниваете двух учащихся в позициях 0 и 1. Если левый учащийся (позиция 0) выше, вы меняете их местами. Если выше правый учащийся, они остаются на своих местах. Затем переходите на одну позицию вправо и сравниваете учащихся в позициях 1 и 2. Опять же если левый учащийся выше, то меняете их местами.

В рамках алгоритма пузырьковой сортировки существуют следующие этапы которые нужно пройти для успешного упорядочивания:

  1. Сравнить двух игроков
  2. Если левый игрок выше, поменять их местами
  3. Перейти на одну позицию вправо

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

6456.eps_2_res_compress.png

Как только вы встретите самого высокого учащегося, вы будете переставлять его при каждом сравнении, пока в конечном итоге он не перейдет в крайнюю правую позицию. Именно поэтому алгоритм и назвали пузырьковой сортировкой. Шаг за шагом самый большой элемент, идентично пузырьку в воде, всплывает до конца некоторого множества.

Теперь алгоритм возвращается к началу шеренги и начинает следующий проход. Он снова перемещается слева направо, сравнивая элементы и переставляя их при необходимости. На этот раз перебор останавливается за один элемент до конца, в позиции 4 на рисунке номер 3, потому что последняя позиция в любом разе содержит наибольший элемент. Процесс продолжается до тех пор, пока все элементы не будут отсортированы.

Реализация

Создадим файл “bubble_function.php”, а в нем объявим функцию которая будет выполнять сортировку

1 <?php
2
3 function bubble_sort(array &$arr) : void {
4     for ($out = count($arr) - 1; $out > 1; $out--) {
5         for ($in = 0; $in < $out; $in++) {
6             if ($arr[$in] > $arr[$in + 1]) {
7                 $temp = $arr[$in];
8                 $arr[$in] = $arr[$in + 1];
9                 $arr[$in + 1] = $temp;
10             }
11         }
12     }
13 }

Разбор

  • В третьей строке была объявлена функция с именем bubble_sort, которая принимает в качестве параметра массив. Обратите внимание, что переменная массива будет передаваться по ссылке
  • В четвертой строке продекларирован внешний цикл, который отвечает за проход по всему массиву. Количество шагов (итераций) зависит от того, сколько элементов расположено в массиве. Переменная “$out” содержит номер позиции элемента в структуре до которого стоит производить сравнение. Каждая итерация уменьшает количество шагов на одну единицу. Цикл прекращает работу тогда, когда были рассмотрены все элементы массива
  • В пятой строке объявлен внутренний цикл который отвечает за проход по каждому из элементов за исключением тех, которые уже были отсортированы.
  • В шестой строке производится проверка является ли значение элемента в текущей позиции больше соседнего
  • В блоке кода расположенном между седьмой и девятой строками производится перемещение элементов

Давайте создадим файл “sort_bubble.php”, подключим в него описанную ранее функцию пузырьковой сортировки и воспользуемся ей

1  <?php
2
3  require __DIR__ . '/bubble_function.php';
4
5  $set = $argv[1];
6
7  echo "$set \n";
8
9  $arr = explode(',', $set);
10
11 bubble_sort($arr);
12
13 echo implode(', ', $arr) . "\n";

Разбор

  • В третьей строке кода мы подключаем написанную ранее функцию пузырьковой сортировки
  • В пятой строке мы присваиваем переменной “$set” введенный пользователем числовой ряд
  • В седьмой строке мы производим вывод введенного пользователем числового ряда
  • В девятой строке мы превращаем числовой ряд в массив
  • В одиннадцатой строке кода производится сортировка посредством написанной нами функции
  • В тринадцатой строке мы выводим отсортированный числовой ряд

Проверим работоспособность написанной программы

php sort_bubble.php "10,1,9,21,3,34,4,22"

10,1,9,21,3,34,4,22
1, 3, 4, 9, 10, 21, 22, 34

Как видим, сортировка была выполнена успешно

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

Информация

Автор конспекта


Дата создания: 04.01.2019
Категория: Алгоритмы и структуры данных