Что такое пузырьковая сортировка. Сортировка пузырьком
Расположим массив сверху вниз, от нулевого элемента - к последнему.
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию...
Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
Template
Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n 2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать.
Чем мы сейчас и займемся.
Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит?
Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла(особенно, если массив был отсортирован с самого начала!).
Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.
Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.
Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.
Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой ".
Template
Насколько описанные изменения повлияли на эффективность метода? Среднее количество сравнений, хоть и уменьшилось, но остается O(n 2), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным.
Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.
Сегодня мы затронем тему сортировки в Паскале. Есть достаточно много различных методов, большинство из них не имеет широкой известности, да и знание их в принципе и не нужно. Достаточно знать базовый набор и несколько дополнительных. В этой статья я расскажу вам о самой известной сортировке - это сортировка методом пузырька, которую также называют сортировкой простого обмена.
Для начала, что такое сортировка в паскале и зачем она нужна? Сортировка - это метод упорядочить массив (обычно по возрастанию или убыванию) . В задачах встречаются такие строки "расположить элементы массива, начиная от минимального (максимального)" . Имейте ввиду, что это то же самое.
Вернемся к сортировке пузырьком. Почему ее назвали именно так? Дело в том, что это аналогия. Представьте себе обычный массив, расположенный вертикально. В результате сортировки более меньшие элементы поднимаются вверх. То есть здесь массив можно представить в виде воды, а меньшие элементы в виде пузырька, которые всплывают наверх.
Теперь подробнее о самом алгоритме. Все достаточно просто:
1. Для сортировки используется 2 цикла, один вложен в другой. Один используется на шаги, другой на под-шаги.
2. Суть алгоритма - это сравнение двух элементов. Именно двух. Поясняю, например имеем массив с 10-ю элементами. Элементы будут сравниваться парами: 1 и 2, 2и 3,3 и 4,4 и 5,6 и 7 и т.д. При сравнении пар, если предыдущий элемент оказался больше чем последующий - то их меняют местами. Например если второй элемент равен 5 , а третий 2 , то они их поменяют местами.
3. Сортировка методом пузырька делится на шаги. В каждом шаге выполняется попарное сравнение. В результате каждого шага наибольшие элементы начинают выстраиваться с конца массива. То есть после первого шага самый большой по значению элемент массива будут стоять на последнем месте. Во втором шаге работа производится со всеми элементами кроме последнего. Опять находится самый большой элемент и ставится в конец массива, с которым производится работа. Третий шаг повторяет второй и так до тех пор, пока массив не будет отсортирован. Для более удобного восприятия приведу нагядный пример. Возьмем массив, состоящий из 7 элементов: 2,5,11,1,7,8,3. Смотрим.(Кликните на картинку для увеличения изображения)
Перейдем непосредственно к коду. Как уже было сказано нам необходимо два цикла. Вот как это будет выглядеть
const
m = 7; {колличетво элементов в массиве}
var
msort: array 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 then begin
k:= msort[j];
msort[j] := msort;
msort := k;
end;
Write("Отсортированный массив: ");
for i:= 1 to m do
write(msort[i]:4);
end.
Обратите внимание на элемент k . Он нужен только для одной цели: чтобы поменять два элемента массива местами. Дело в том, что в Паскале нет специальной функции, которая бы выполняла такое действие. Поэтому приходится расписывать ее самому, добавляя дополнительный элемент для обмена. На этом статья сортировка методом пузырька закончена, следующие статьи выйдут в течении следующей недели (а может и раньше).
Всем привет!
Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка - это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.
Существуют различные алгоритмы сортировки. Некоторые, хорошо сортируют большое количество элементов, другие, более эффективны при очень маленьком количестве элементов. Наш метод пузырька характерен:
Плюсы:
- Простота реализации алгоритма
- Красивое название
- Один из самых медленных методов сортировки (Время выполнения квадратично зависит от длины массива n 2)
- Почти не применяется в реальной жизни (используется в основном в учебных целях)
Алгоритм: Берем элемент массива, сравниваем со следующим, если наш элемент, больше следующего элемента, то мы их меняем местами. После прохождения всего массива, мы можем быть уверены, что максимальный элемент будет "вытолкнут" - и стоять самым последним. Таким образом, один элемент у нас уже точно стоит на своём месте. Т.к. нам надо их все расположить на свои места, следовательно, мы должны повторить данную операцию, столько раз, сколько у нас элементов массива минус 1. Последний элемент встанет автоматически, если остальные стоят на своих местах.
Вернемся к нашему массиву:3 1 4 2
Берем первый элемент "3" сравниваем со следующим "1". Т.к. "3" > "1", то меняем местами:
1 3 4 2
Теперь сравниваем "3" и "4", тройка не больше четвёрки, значит ничего не делаем. Далее, сравниваем "4" и "2". Четыре больше, чем два - значит меняем местами: 1 3 2 4
. Цикл закончился. Значит самый большой элемент уже должен стоять на своём месте!! Видим, что у нас так и произошло. Где бы "4" (наш самый большой элемент) не находился - он всё равно, после прохождения циклом всего массива, будет последним. Аналогия - как пузырёк воздуха всплывает в воде - так и наш элемент, всплывает в массиве. Поэтому и алгоритм, называется "Пузырьковая сортировка". Чтобы расположить следующий элемент, необходимо, начать цикл сначала, но последний элемент можно уже не рассматривать, потому что он стоит на своём месте.
Сравниваем "1" и "3" - ничего не меняем.
Сравниваем "3" и "2" - Три больше двух, значит меняем местами. Получается:1 2 3 4 . Второй цикл закончили. Мы сделали уже два цикла - значит, с уверенностью можно сказать, что у нас, два последних элемента уже отсортированы. Осталось нам отсортировать третий элемент, а четвёртый, встанет в нужное место, автоматически. Ещё раз, сравниваем первый элемент и второй - видим, что у нас уже всё на своих местах, значит, массив, можно считать, отсортированный по возрастанию элементов.
Теперь осталось запрограммировать данный алгоритм на языке Pascal.
const n = 4; {Заводим константу, это будет длина массива}
var i, j, k:integer; {Две переменные для вложенного цикла, одна для того чтобы элементы менять местами }
m:array of integer; {Заводим массив}
begin
{Будем запрашивать массив с клавиатуры:}
Writeln("Введите массив:");
for i:=1 to n do begin
Writeln(i, " элемент:");
Readln(m[i]);
end;
{Внешний цикл отвечает за то, что мы должны повторить
внутренний цикл столько раз, сколько у нас элементов
массива минус 1.}
for i:=1 to n-1 do begin
{Внутренний цикл уже перебирает элементы и сравнивает между собой.}
for j:=1 to n-i do begin
{Если элемент, больше следующего, то меняем местами.}
if m[j]>m then begin
k:=m[j];
m[j]:=m;
m:=k;
end;
end;
end;
{Выводи результат:}
for i:=1 to n do
Write(m[i], " ");
end.
Вот результат:
А вот видеоурок
Сортировка пузырьком – простейший алгоритм сортировки, применяемый чисто для учебных целей. Практического применения этому алгоритму нет, так как он не эффективен, особенно если необходимо отсортировать массив большого размера. К плюсам сортировки пузырьком относится простота реализации алгоритма.
Алгоритм сортировки пузырьком сводится к повторению проходов по элементам сортируемого массива. Проход по элементам массива выполняет внутренний цикл. За каждый проход сравниваются два соседних элемента, и если порядок неверный элементы меняются местами. Внешний цикл будет работать до тех пор, пока массив не будет отсортирован. Таким образом внешний цикл контролирует количество срабатываний внутреннего цикла Когда при очередном проходе по элементам массива не будет совершено ни одной перестановки, то массив будет считаться отсортированным. Чтобы хорошо понять алгоритм, отсортируем методом пузырька массив, к примеру, из 7 чисел (см. Таблица 1).
исходный массив: 3 3 7 1 2 5 0
| № итерации | Элементы массива | Перестановки | ||||||
|---|---|---|---|---|---|---|---|---|
| исх. массив | 3 | 3 | 7 | 1 | 2 | 5 | 0 | |
| 0 | 3 | 3 | false | |||||
| 1 | 3 | 7 | false | |||||
| 2 | 1 | 7 | 7>1, true | |||||
| 3 | 2 | 7 | 7>2, true | |||||
| 4 | 5 | 7 | 7>5, true | |||||
| 5 | 0 | 7 | 7>0, true | |||||
| тек. массив | 3 | 3 | 1 | 2 | 5 | 0 | 7 | |
| 0 | 3 | 3 | false | |||||
| 1 | 1 | 3 | 3>1, true | |||||
| 2 | 2 | 3 | 3>2, true | |||||
| 3 | 0 | 3 | 3>0, true | |||||
| 4 | 3 | 5 | false | |||||
| 5 | 5 | 7 | false | |||||
| тек. массив | 3 | 1 | 2 | 0 | 3 | 5 | 7 | |
| 0 | 1 | 3 | 3>1, true | |||||
| 1 | 2 | 3 | 3>2, true | |||||
| 2 | 0 | 3 | 3>0, true | |||||
| 3 | 3 | 3 | false | |||||
| 4 | 3 | 5 | false | |||||
| 5 | 5 | 7 | false | |||||
| тек. массив | 1 | 2 | 0 | 3 | 3 | 5 | 7 | |
| 1 | 2 | false | ||||||
| 0 | 2 | 2>0, true | ||||||
| 2 | 3 | false | ||||||
| 3 | 3 | false | ||||||
| 3 | 5 | false | ||||||
| 5 | 7 | false | ||||||
| тек. массив | 1 | 0 | 2 | 3 | 3 | 5 | 7 | |
| 0 | 1 | 1>0, true | ||||||
| 1 | 2 | false | ||||||
| 2 | 3 | false | ||||||
| 3 | 3 | false | ||||||
| 3 | 5 | false | ||||||
| 5 | 7 | false | ||||||
| конечный массив | 0 | 1 | 2 | 3 | 3 | 5 | 7 | |
| Конец сортировки | ||||||||
Для того чтобы отсортировать массив хватило пяти запусков внутреннего цикла, for . Запустившись, цикл for срабатывал 6 раз, так как элементов в массиве 7, то итераций (повторений) цикла for должно быть на одно меньше. На каждой итерации сравниваются два соседних элемента массива. Если текущий элемент массива больше следующего, то меняем их местами. Таким образом, пока массив не будет отсортирован, будет запускаться внутренний цикл и выполняться операция сравнения. Обратите внимание на то, что за каждое полное выполнение цикла for как минимум один элемент массива находит своё место. В худшем случае, понадобится n-2 запуска внутреннего цикла, где n – количество элементов массива. Это говорит о том, что сортировка пузырьком крайне не эффективна для больших массивов.
Разработаем программу, в которой сначала необходимо ввести размер одномерного массива, после чего массив заполняется случайными числами и сортируется методом пузырька.
// bu_sort.cpp: определяет точку входа для консольного приложения.
#include "stdafx.h"
#include
Результат работы программы показан на рисунке 1.
Рисунок 1 — Сортировка пузырьком
Алгоритм сортировки одномерного массива методом «пузырька». Описание алгоритма. Блок-схема и программа сортировки по возрастанию массива типа real из 7 элементов.
Описание алгоритма
Классификация методов сортировки не всегда четко определена. Остановимся на методе, в котором обмен двух элементов является основной характеристикой процесса. Приведенный ниже алгоритм сортировки простым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы.
Как и в предыдущих методах простого выбора, мы совершаем повторные проходы по массиву, каждый раз просеивая наименьший элемент оставшегося множества, двигаясь к левому концу массива. Если, для разнообразия, мы будем рассматривать массив, расположенный вертикально, а не горизонтально и – при помощи некоторого воображения - представим себе элементы пузырьками в резервуаре с водой, обладающими «весами», соответствующими их ключам, то каждый проход по массиву приводит к «всплыванию» пузырька на соответствующий его весу уровень (см. табл. 2). Этот метод широко известен как сортировка методом пузырька . Его простейший вариант приведен в программе 1.
Пример сортировки методом пузырька
procedure bubblesort ;
var i , j : index ; x : item ;
begin for i := 2 to n do
begin for j := n downto i do
if a [j -1].key > a [j ].key then
begin x := a [j -1]; a [j -1] := a [j ]; a [j ] := x
end {bubblesort }
Сортировка методом пузырька
Этот алгоритм легко оптимизировать. Пример в табл. 2 показывает, что три последних прохода никак не влияют на порядок элементов, поскольку те уже рассортированы. Очевидный способ улучшить данный алгоритм – это запоминать, производился ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм можно продолжить, если запоминать не только сам факт обмена, но и место (индекс) последнего обмена. Ведь ясно, что все пары соседних элементов с индексами, меньшими этого индекса k , уже расположены в нужном порядке. Поэтому следующие проходы можно заканчивать на этом индексе, вместо того чтобы двигаться до установленной заранее нижней границыi . Однако внимательный программист заметит здесь странную асимметрию: один неправильно расположенный «пузырек» в «тяжелом» конце рассортированного массива всплывает на место за один проход, а неправильно расположенный элемент в «легком» конце будет опускаться на правильное место только на один шаг на каждом проходе. Например, массив
12 18 42 44 55 67 94 06
будет рассортирован при помощи метода пузырька за один проход, а сортировка массива
94 06 12 18 42 44 55 67
потребует семи проходов. Эта неестественная асимметрия подсказывает третье улучшение: менять направление следующих один за другим проходов.
Анализ сортировки методом пузырька.
Число сравнений в алгоритме простого обмена равно
,
минимальное, среднее и максимальное количества пересылок (присваиваний элементов) равны
,
,
.
Блок–схема сортировки методом пузырька.
Программа сортировки
A: array of real;
N, j, k: integer;
WriteLn("Ввод массива");
for j:= 1 to N do
Write("A", j, "=");
WriteLn("Исходный массив");
for j:= 1 to N do
Write(A[j]:8:1);
for j:= 2 to k do
if A > A[j] then
A := A[j];
WriteLn("Отсортированный массив");
for j:= 1 to N do
Write(A[j]:8:1);
