heap.tech
лаборатория велосипедов
×

Bubble sorting algorithm. Пузырьковая сортировка

16 февраля 2016
Каждый программист должен изобрести собственный велосипед или хотя-бы добавить костыль в чужой и, естественно, назвать это идеальным кодом.
Если рассматривать велосипед как средство передвижения, а каждого программиста как проектировщика - то каждый проектировщик хочет сделать свой велосипед круче, чем у других. Он будет стремиться сделать более эргономичную раму, удобное сиденье трещотку на спицы, чтобы как мопед звучал и т.д. Но сам принцип работы велосипеда, основные узлы, например, колесо, подшипники, принцип работы переключателя скоростей, тормоза - неизменны. Это базовые принципы, они были изобретены и отлажены такими-же мастерами велостроения задолго до появления нашего программиста-проектировщика, поэтому необходимости придумывать круглое колесо и цепную передачу у него нет.
Тоже и в программировании - есть базовые фичи, облегчающие жизнь при создании новой программы. Это может быть выборка чего-то из чего-то, поиск и исключение дубликатов, сортировка, группировка, сборка мусора и т.д. Все эти фичи позволяют упростить создание программы, но редко кто задумывается, а как именно работает, например, сортировка массива в прямом или обратном порядке.

Но вот настал сферический час икс в вакууме, когда нет ничего вроде Array.Sort(), Array.Reverse() и типа того. Придется изобретать это заново. И тут два пути – первый это придумывать алгоритм сортировки с 0 самостоятельно или взять уже существующий отлаженный алгоритм.
Первый вариант это провал – потребуется убить кучу времени для понимания размеров массива, реализации лучшего алгоритма для лучшей производительности и последующей отладки. А результат, если таковой вообще будет, ничем не будет отличаться от результата, полученного вторым путем. За исключение пары недель убитого впустую времени.
Поэтому идеально держать в голове основные алгоритмы или, хотя-бы, знать что такие вообще существуют.
Начнем с академического алгоритма сортировки массива Bubble sorting. Он же пузырьковая сортировка. Называется он так, потому что каждый элемент массива постепенно всплывает на то место, где он должен находиться.
Для примера я буду использовать javascript - это достаточно выразительно + можно покрутить и отладить в любом браузере.

Алгоритм

function BubbleSort(arr) { var len = arr.length; var temp; for (var i = len - 1; i >= 0; i--) { for (var j = 1; j <= i; j++) { if (arr[j - 1] > arr[j]) { temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; } } } return; } BubbleSort ([6,4,1,8,3]);

Итак - два цикла, верхний (i) и нижний (j). Число проходов равно длине массива, в нашем случае - это 5. Для каждой итерации верхнего цикла происходит Х-1 итераций нижнего цикла, где Х – это итератор из верхнего цикла (который в свою очередь может быть больше или равен 0 и меньше 5).
Каждый проход нижнего цикла сравнивает два числа из рядом стоящих ячеек массива, если одна ячейка больше другой – меняем местами эти ячейки (для этого используется переменная temp, она хранит значение предыдущей ячейки). К концу первой итерации внешнего цикла самое большое число будет в самом конце массива, но остальные числа все еще могут быть не отсортированы. Поэтому следующий проход вложенного цикла будет равен длинне массива минус один.
Да, в javascript массивы это ссылочные типы – не нужно возвращать значение, исходный массив уже отсортирован, с ним можно продолжить работу.
Слегка улучшим алгоритм – добавим порядок сортировки (сортировать массив по убыванию или по возрастанию)

function bubbleSort(arr, byDesc) { var len = arr.length; var temp; var i, j; var sortCondition = function (v1, v) { if (byDesc) return (v1 > v); else return (v1 < v); }; for (i = 0; i < len; i++) { for (j = i; j >= 0; j--) { if (sortCondition(arr[j + 1], arr[j])) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } return; }

В этом примере я немного поменял условия циклов. Верхний цикл работает в интервале от 0 до длины массива, в нашем случае до 5. Нижний цикл в интервале от значения итератора верхнего цикла до 0 включительно. Естественно я изменил адресацию ближних ячеек (arr[j-1] вместо arr[j+1]) в нижнем цикле.
Кроме этого я добавил переменную sortCondition - делегат. sortCondition принимает два значения близлежащих ячеек и возвращает true или false, в соответствии с тем, какой порядок сортировки был передан в функцию bubbleSort.
Из делегата sortCondition видно, что для сортировки по возрастанию нужно чтобы значение ячейки с большим индексом было меньше значения ячейки с меньшим. И наоборот, для сортировки по убыванию значение ячейки с большим индексом должно быть больше значения ячейки с меньшим.
Для проверки работы алгоритма можно скопипастить это и смотреть вывод в консоли.

var shakedArray = [2,9,4,6]; console.log('source array: ' + shakedArray); bubbleSort(shakedArray); console.log('asc: ' + shakedArray); bubbleSort(shakedArray, true); console.log('desc: ' + shakedArray);

Плюсы
1. Он простой
Минусы
1. Даже если массив из 6 ячеек не нуждается в сортировке - алгоритм будет запускать два цикла и выполнять 21 сравнение. Тоже самое, если число перестановок в массиве из 6 ячеек будет равно одному, то все равно будет 21 итерация внутреннего цикла.
2. Количество переназначений ячеек. Они (ячейки) в самом худшем варианте будут переназначаться 15 раз (в массиве из 6 ячеек). Кол-по переназначений можно расчитать по формуле (N-1) * (N / 2). Где N - это длинна массива.
 
1678
0

Оставлять комментарии могут только зарегистрированные пользователи

пока никто не оставлял комментариев