Если вы не читали мои предыдущие посты из серии, то там рассказывается о том, как я научился писать Bash-скрипты без компьютера, то есть прочитав книгу Командная строка Linux Уильяма Шоттса (2-е изд., No Starch Press) и записывать сценарии карандашом и листами бумаги. На практике я применил то, что узнал из книги, для написания некоторых элементарных алгоритмов сортировки, игры Виселица и игры Крестики-нолики, которые впоследствии были проверены на работоспособность. Пожалуйста, обратитесь к Части 1 и Части 2 этой серии, если вы хотите узнать больше о том, как я попал в сценарии оболочки и о двух других алгоритмах сортировки, которые я написал на Bash.
Алгоритм пузырьковой сортировки
Три алгоритма сортировки, о которых я буду говорить, сортировка выбором, сортировка вставками и, здесь, пузырьковая сортировка, имеют в худшем случае O(n²) временную сложность; в то время как сортировка выбором остается в лучшем случае на n² (таким образом, θ(n²)), два других вида в лучшем случае имеют Ω(n), если сортируемый список уже находится в заказ. Опять же, это вопросы DSA, которые здесь не рассматриваются. Я просто хочу выбросить их, чтобы люди не задумывались о производительности.
Так как же работает пузырьковая сортировка? Подобно сортировке выбором и вставкой, пузырьковая сортировка повторяется от начала/слева к концу/справа списка. Однако, в отличие от двух других сортировок, в которых отсортированный подсписок находится слева, пузырьковая сортировка имеет отсортированный подсписок справа. Он сравнивает первый элемент со вторым элементом в списке и меняет их местами, если первый больше второго, а затем продолжает сравнивать второй элемент с третьим и так далее, пока не достигнет границы отсортированного подсписка. вправо, который начинается пустым и расширяется на одну позицию влево при каждой итерации. Пузырьковая сортировка получила свое название, потому что на каждой итерации самый большой элемент в несортированном подсписке всплывает до конца списка. Это противоположно тому, как работает сортировка вставками. На каждой итерации сортировка вставками сравнивает n-й элемент с (n-1)-м и меняет их местами, если n-й элемент меньше чем (n-1)-й, а затем продолжает сравнивать (n-1)-й элемент с (n-2 )th и так далее, пока не достигнет границы отсортированного подсписка слева. Знание этой разницы поможет нам подумать о том, как повысить производительность пузырьковой сортировки по сравнению с сортировкой вставками.
Чтобы визуализировать сортировку, давайте проиллюстрируем тот же список целых чисел, который мы использовали:
5 3 9 20 56 4 11
Сортировка начинается с чисел 5 и 3 в первой итерации, сравнивается и меняет их местами, чтобы сдвинуть 5 вправо. Затем он сравнивает числа 5 и 9, 9 и 20, 20 и 56 и оставляет их на месте, потому что первое не больше второго в каждом сравнении. Далее он сравнивает 56 и 4 и меняет их местами, чтобы переместить 56 вправо, а затем сравнивает 56 и 11 и меняет их местами, чтобы снова переместить 56 вправо, в результате чего список выглядит следующим образом:
3 5 9 20 4 11 56
Следующая итерация остановится перед числом 56, которое сейчас находится в отсортированном подсписке. Он начинается с цифр 3 и 5 и оставляет их на месте. То же самое с числами 5 и 9, 9 и 20. Затем он меняет местами 20 и 4, а также 20 и 11 и останавливается, потому что достиг границы отсортированного подсписка, который теперь включает 20 и 56 и выглядит следующее:
3 5 9 4 11 20 56
Следующая итерация остановится перед числом 20 и начнется со сравнения 3 и 5, а затем 5 и 9 и оставит три числа на месте. Однако затем он сравнивает и меняет местами 9 и 4 с пузырьком 9 справа, переходит к сравнению 9 и 11 и оставляет их на месте, прежде чем остановиться на границе отсортированного подсписка, который теперь включает 11, 20 и 56 и выглядит следующим образом:
3 5 4 9 11 20 56
Следующая итерация остановится перед числом 11, начнется со сравнения 3 и 5 и оставит их на месте. Затем он сравнивает 5 и 4 и меняет их местами, чтобы переместить 5 вправо, и продолжает сравнивать 5 и 9 и оставляет их на месте, прежде чем остановиться. Отсортированный подсписок теперь включает 9, 11, 20 и 56 и выглядит следующим образом:
3 4 5 9 11 20 56
Хотя список в этом примере теперь отсортирован, есть и другие экземпляры, в которых наименьший элемент начинается в крайнем правом углу и его необходимо менять местами на каждой итерации, чтобы он перемещался в крайнее левое положение, чтобы быть в порядке. В любом случае сортировка без инструкций в противном случае продолжит сравнение без замены чисел 3 и 4, а затем 4 и 5, чтобы завершить следующую итерацию, которая в конце будет включать 5, 9, 11, 20 и 56 в число. отсортированный подсписок.
И последняя итерация выполнит сравнение чисел 3 и 4 и, наконец, сделает вывод, что список теперь в порядке, несмотря на то, что это уже было, поэтому нам нужно добавить какой-то механизм прерывания для повышения производительности в случае ошибки. список становится отсортированным перед (n-1)-й итерацией — n – это длина списка, а n - 1 – потому что последний элемент не будет иметь никого, с кем можно было бы сравнить и/или поменять местами.
Википедия иллюстрирует пузырьковую сортировку следующим GIF:
Сценарий оболочки
Давайте подумаем, как можно реализовать пузырьковую сортировку. Представляется, что он включает в себя следующие предпосылки:
- Это итеративный процесс, указывающий на использование цикла или циклов.
- Количество итераций не более n - 1, где n – это длина списка.
- Он сравнивает каждый элемент со следующим и меняет их местами или нет.
- Количество элементов, участвующих в каждой итерации, уменьшается на 1.
Поскольку сортировка вставками работает аналогично сравнению и обмену каждым элементом с его соседом, и отличается только тем, что работает в обратном направлении влево — здесь мы работаем вперед вправо — я сначала попытался использовать ту же структуру вложенных циклов. Для начала я объявил функцию bubble_sort и в ней присвоил аргумент — который будет списком целых чисел — локальному массиву arr, чтобы я мог сортировать и возвращать список отсортирован, не затрагивая исходный массив. Затем с расширением параметра я присвоил длину массива arr переменной n следующим образом:
!#/bin/bash
function bubble_sort () {
local arr=($@)
n=${#arr[@]}
# nested for loops
}
Опять же, не забудьте shebang, который объявляет путь к интерпретатору Bash, который будет использоваться для выполнения файла. $@ расширяет переданный функции аргумент, а заключение его в круглые скобки делает его массивом, который будет присвоен локальной переменной arr. ${#arr[@]} расширяется, чтобы получить количество arr[@], которое расширяется, чтобы извлечь список целых чисел, содержащихся в arr. Вам не обязательно иметь локальный arr, если вы хотите отсортировать глобальный массив на месте.
Итак, как я могу использовать вложенные циклы для выполнения сортировки? Я использовал первый (внешний) цикл, чтобы установить максимальное количество итераций для выполнения и запомнить смещение последнего индекса, по которому следует выполнять сравнение и замену.
Как насчет внутреннего цикла? Поскольку отсортированный подсписок находился справа и рос с каждой итерацией, на каждой итерации сравнение и замена должны были начинаться с первого элемента, но останавливаться перед границей отсортированного подсписка, который начинается пустым — вот почему мне нужно смещение с конца списка во внешнем цикле, чтобы прекратить работу во внутреннем цикле. Поэтому я пошел:
function bubble_sort () {
local arr=($@)
n=${#arr[@]}
for (( i=0; i<$((n-1)); i++ )); do
for (( j=0; j<$((n-i-1)); j++ )); do
# logic to compare and swap
done
done
}
Условие для внешнего цикла состоит в том, чтобы начинаться со счетчика 0 — отсортированный подсписок начинался пустым — и заканчиваться до n - 1, потому что у последнего элемента не было соседа справа для сравнения и/или замены с ним. . Внутренний цикл должен начинаться с индекса 0 — индексы для итерируемого объекта всегда начинаются с 0 — и заканчиваются за одну позицию до границы отсортированного подсписка — смещение начинается с 0 справа и увеличивается на 1 для каждой последующей итерации. Проще говоря, здесь мы говорим: запустить n - 1 раз и при каждом запуске выполнять определенные операции n – 1 – i раз, i strong> для увеличения на 1 от 0 до n - 1. Мы используем двойные круглые скобки (( )) для заключения условных операторов цикла for и знака доллара, за которыми следуют двойные круглые скобки $(( )) для переноса и расширения арифметических операций. выражения в Баше. Затем я применил шаблон сравнения-и-перестановки-если из сортировки вставками:
function bubble_sort () {
local arr=($@)
n=${#arr[@]}
for (( i=0; i<$((n-1)); i++ )); do
for (( j=0; j<$((n-i-1)); j++ )); do
if (( ${arr[j]} > ${arr[j+1]} )); then
temp=${arr[j]}
arr[j]=${arr[j+1]}
arr[j+1]=$temp
fi
done
done
}
Условная логика точно такая же, как и в сортировке вставками, которая говорит, что если элемент arr[j] больше, чем arr[j+1], поменять их местами. ! Логика замены элементов одинакова для всех трех типов, которые я представил до сих пор. Мне пришлось использовать переменную-заполнитель temp для хранения значения одного элемента массива, чтобы поменять местами значения обоих, потому что Bash не предоставляет механизма деструктурирования присваиваний, который может перекрестно присваивать значения двух переменных в массиве. одно выражение.
Затем я выводил отсортированный список в стандартный вывод (STDOUT), т. е. в терминал или командную строку, с помощью команды echo и вызывал функцию bubble_sort с помощью массив, созданный глобально, с последующим выводом содержимого несортированного массива в STDOUT для сравнения.
#!/bin/bash
function bubble_sort () {
local arr=($@)
n=${#arr[@]}
for (( i=0; i<$((n-1)); i++ )); do
for (( j=0; j<$((n-i-1)); j++ )); do
if (( ${arr[j]} > ${arr[j+1]} )); then
temp=${arr[j]}
arr[j]=${arr[j+1]}
arr[j+1]=$temp
fi
done
done
echo Sorted array: ${arr[@]}
}
arr=(5 3 9 20 56 4 11)
bubble_sort ${arr[@]}
echo Original array: ${arr[@]}
Команда echo просто выводит все, что вы ей передаете, в STDOUT — здесь элементы локального массива arr, извлеченные с расширением параметра ${arr[@]}. STDOUT и STDIN (стандартный ввод) означают вывод на терминал или ввод с него.
На шаге выше я создал глобальный массив arr с тем же списком, который я использовал для иллюстрации ранее, и вызвал функцию с его содержимым в качестве аргумента. Затем я вывел содержимое массива, чтобы сравнить его с отсортированным массивом, который будет напечатан предыдущим вызовом функции.
Сделайте файл исполняемым, запустите его в терминале, и вы должны увидеть следующее: (при условии, что имя файла bubble_sort.sh и вы выполняете команды в той же папке, что и файл в дереве каталогов )
$ chmod 755 ./bubble_sort.sh $ ./bubble_sort.sh Sorted array: 3 4 5 9 11 20 56 Original array: 5 3 9 20 56 4 11
chmod 755 по существу аналогичен chmod a+x для этой цели, за исключением того, что первый явно указывает, что только владелец файла (автор) имеет доступ на запись к это, тогда как последний только добавляет исполняемости для других.
Но мы можем сделать лучше. Помните, список был отсортирован после четвертой итерации? Функция в том виде, в каком она написана сейчас, будет иметь два пробных прогона, в которых она сначала сравнит 3 и 4, затем 4 и 5 в одном прогоне и снова 3 и 4 в другом, прежде чем выйти из цикла к Эхо отсортированный список. Представьте, если бы я использовал программу для сортировки очень длинного списка, который сортируется на полпути при выполнении циклов. Было бы действительно неэффективно продолжать выполнение циклов с этой точки.
Так что я мог сделать? В сортировке вставками я остановил внутренний цикл на короткое время и начал следующую итерацию, как только arr[j+1] стало не меньше, чем arr[j], потому что цикл собирался слева разместить arr[j+1] в правильном порядке отсортированного подспискаслева . Здесь я не мог этого сделать, потому что при пузырьковой сортировке отсортированный подсписок находился справа, а внутренний цикл работал только с несортированным подсписком слева — я не мог подобрать из двух элементов там, чтобы сказать, все ли остальное в порядке.
Решение, которое я придумал, состояло в том, чтобы сделать снимок массива перед запуском внутреннего цикла и сравнить его с массивом, прошедшим внутренний цикл. Если два массива были одинаковыми, я знал, что массив был отсортирован, и останавливал циклы:
function bubble_sort () {
local arr=($@)
n=${#arr[@]}
for (( i=0; i<$((n-1)); i++ )); do
fore=${arr[@]}
for (( j=0; j<$((n-i-1)); j++ )); do
if (( ${arr[j]} > ${arr[j+1]} )); then
temp=${arr[j]}
arr[j]=${arr[j+1]}
arr[j+1]=$temp
fi
done
if [[ ${arr[@]} == $fore ]]; then
break
fi
done
echo Sorted array: ${arr[@]}
}
Условное выражение (называемое «тестом» в Bash) оператора if может быть заключено в пару квадратных скобок или, для более сложных выражений, таких как здесь, в пару двойных скобок [ [ ]] — и двойные скобки (( )) для арифметических вычислений. Я всегда использовал двойные скобки или двойные круглые скобки, чтобы быть в безопасности.
Таким образом, fore был моментальным снимком, сделанным перед запуском внутреннего цикла в массиве. И я сравнил его со снимком массива, прошедшим цикл (т. е. ${arr[@]} в операторе if). Я разорвал внешний цикл, если они были одинаковыми. Это предотвратило бы пробные прогоны после того, как список был отсортирован.
Вы можете поместить следующий оператор перед разрывом цикла, чтобы убедиться, что он действительно работает.
#!/bin/bash
function bubble_sort () {
local arr=($@)
n=${#arr[@]}
for (( i=0; i<$((n-1)); i++ )); do
fore=${arr[@]}
for (( j=0; j<$((n-i-1)); j++ )); do
if (( ${arr[j]} > ${arr[j+1]} )); then
temp=${arr[j]}
arr[j]=${arr[j+1]}
arr[j+1]=$temp
fi
done
if [[ ${arr[@]} == $fore ]]; then
echo Sorting stopped at the $((n+1))th iteration
break
fi
done
echo Sorted array: ${arr[@]}
}
arr=(5 3 9 20 56 4 11)
bubble_sort ${arr[@]}
echo Original array: ${arr[@]}
Если вы снова запустите скрипт, вы должны увидеть в STDOUT следующее:
Sorting stopped at the 5th iteration Sorted array: 3 4 5 9 11 20 56 Original array: 5 3 9 20 56 4 11
Внешний цикл выполняет не более шести итераций — n - 1, где n — это длина (7) списка. Мы сохранили только один пробный прогон из нескольких операций, но мы могли бы сэкономить гораздо больше, если бы список был больше и реалистичнее, сортируясь на полпути.
Подведение итогов
Я надеюсь, что вы продолжаете получать удовольствие от чтения моих постов. И если у вас есть, пожалуйста, оставьте знак, чтобы у меня был стимул продолжить и завершить серию сценариев оболочки и продолжить писать больше о моем путешествии по программированию. Я уверен, что стану более опытным писателем, если буду продолжать.
