Метод пузырьков в информатике — это метод сортировки данных в различных массивах.
Введение
Общеизвестно, что самым быстрым методом сортировки данных в массивах является быстрая сортировка. Но существуют и другие классы сортировки, имеющие свои достоинства и недостатки. Например, сортировка выбором, сортировка вставками, сортировка слиянием, сортировка распределением, гибридная сортировка и параллельная сортировка. Кроме этих классов сортировок, есть ещё обменный способ сортировки, получивший название пузырьковой сортировки. В классе обменных сортировок есть более двенадцати видов различных сортировок, которые имеют тесную взаимосвязь с пузырьковой сортировкой. Упорядочивание (собственно, сортировка) выполняется путём многочисленного последовательного пересмотра данных массива и сравнения отдельных пар компонентов друг с другом. Если элементы, подлежащие сравнению, ещё не проходили сортировку по отношению друг к другу, то надо поменять их местами. Но проблема заключается в том, каким конкретно образом выбирать элементы массива в качестве пар для сравнения и по какому принципу обходить весь массив.
Алгоритм глупой сортировки
Согласно этому алгоритму сортировки, массив просматривается просто слева направо и по ходу идёт сравнение соседних элементов. Если встречаются два неотсортированных элемента, то они меняются местами выполнение алгоритма начинается с начала. Опять идёт анализ массива и если снова встречается «неправильная» пара соседствующих элементов, то они так же меняются местами и происходит возврат к началу алгоритма. Этот процесс продолжается до окончания сортировки массива данных. Это наиболее простой и очевидный способ сортировки, но и наиболее длительный.
Алгоритм пузырьковой сортировки
Внесём в алгоритм глупой сортировки незначительное усовершенствование. При обнаружении на очередном проходе пары неотсортированных элементов, они меняются местами, но алгоритм не начинается с начала, а просмотр элементов просто продолжается дальше до окончания просмотра всего массива. В таком случае мы имеем уже алгоритм, получивший название пузырьковая сортировка. Другое его название — сортировка с помощью простых обменов. Алгоритм работы также достаточно простой, необходимо обходить массив с самого начала и до конца, при этом выполняя обмен местами соседних элементов, которые ещё не отсортированы. В итоге после первого прохода на последнем месте окажется элемент с максимальным значением. Далее выполняется следующий проход неотсортированной части массива, то есть от начального элемента до предпоследнего. Во время прохода снова меняются местами неотсортированные соседние элементы. При этом второй по величине элемент будет перемещён на предпоследнее место. Далее процесс продолжается аналогичным образом, обход будет уменьшаться по длине и максимальные по величине элементы будут помещаться в конец массива.
Метод пузырьковой сортировки в Паскале
Под сортировкой на языке Паскаль понимается упорядочение массива данных (как правило по возрастанию или по убыванию). Сортировка названа пузырьковой из-за аналогии с погруженными в воду вертикальным массивом. Массив — это вода, а его самые маленькие элементы являются пузырьками, которые стремятся всплыть вверх.
Алгоритм может быть представлен следующим образом:
Для выполнения процесса сортировки применяются два цикла, причём один цикл вложен в другой. Первый цикл применяется для формирования шагов, второй — под-шагов.
Основой алгоритма является сравнение двух элементов. К примеру, есть массив с десятью элементами. Элементы подлежат сравнению парами: 1 и 2, 2 и 3, 3 и 4 ,4 и 5 ,6 и 7 и так далее. Если при выполнении сравнения текущий элемент больше по величине чем следующий, то они меняются местами. К примеру, если первый элемент пять, а второй два, то они меняются местами.
Процесс сортировки пузырьковым методом подразделяется на шаги. Каждый шаг предполагает сравнение пары элементов. Итогом работы каждого шага является выстраивание самого большого элемента в конец массива. Таким образом после первого шага наибольший элемент массива окажется на последнем месте. При втором шаге действия выполняются по отношению ко всем элементам, исключая последний. Далее снова ищется наибольший элемент, и он перемещается опять в окончание массива, который в данный момент обрабатывается. И так процесс повторяется до полного окончания сортировки.
Приведём наглядный пример. Имеется массив, включающий в себя семь элементов: 2, 5, 11, 1, 7, 8, 3. Процесс сортировки изображён на рисунке 1.
Рисунок 1. Процесс сортировки. Автор24 — интернет-биржа студенческих работ
Далее сформируем собственно программу, реализующую данный алгоритм на языке Паскаль. Ниже приведён текст программы:
m = 7; {количество элементов в массиве}
var
msort: array[1..m] of integer; {собственно наш массив}
i, j, k: integer; {i - это шаг ,j - это под-шаг}
begin
writeln('Введите элементы массива');
for i := 1 to m do
read(msort[i]);
for i := 1 to m - 1 do
for j := 1 to m - i do
if msort[j] > msort[j + 1] then begin
k := msort[j];
msort[j] := msort[j + 1];
msort[j + 1] := k;
end;
write('Отсортированный массив: ');
for i := 1 to m do
write(msort[i]:4);
writeln;
end.
Следует подчеркнуть, что элемент k нужен только для того, чтобы выполнить обмен местами двух элементов. Это объясняется тем, что Паскаль не имеет команды, которая смогла бы осуществить эту операцию. Это вынуждает формировать данную процедуру программным путём, вводя добавочный элемент для обмена.
Шейкерная сортировка
Другое её название сортировка перемешиванием, или сортировка типа коктейль. Это разновидность пузырьковой сортировки, но с некоторыми отличиями. Начало сортировки полностью совпадает с пузырьковым методом, элементы с максимальным значением отправляются в конец массива. Но затем происходит разворот на сто восемьдесят градусов, и начинается движение в обратном направлении. Но теперь уже ищется и перемещается не максимальное, а минимальное значение элемента.
