Не только не считается самым быстрым методом, более того, она замыкает перечень самых медленных способов упорядочивания. Однако и у нее есть свои плюсы. Так, сортировка методом пузырька - самое что ни на есть логичное и естественное решение проблемы, если необходимо расставить элементы в определенном порядке. Обычный человек вручную, к примеру, воспользуется именно им - просто по интуиции.
Откуда взялось такое необычное название?
Название метода придумали, используя аналогию с воздушными пузырьками в воде. Это метафора. Подобно тому, как маленькие пузыри воздуха поднимаются наверх - ведь их плотность больше, чем какой-либо жидкости (в данном случае - воды), так и каждый элемент массива, чем меньше он по значению, тем больше он постепенно пробирается к началу перечня чисел.
Описание алгоритма
Сортировка пузырьком выполняется следующим образом:
- первый проход: элементы массива чисел берутся по два и также парами сравниваются. Если в какой-то двойке элементов первое значение оказывается больше второго, программа производит их обмен местами;
- следовательно, попадает в конец массива. В то время как все остальные элементы остаются, как и были, в хаотичном порядке и требуют еще сортировки;
- поэтому и необходим второй проход: производится он по аналогии с предыдущим (уже описанным) и имеет число сравнений - минус один;
- у прохода номер три сравнений на единицу меньше, чем у второго, и на двойку, чем у первого. И так далее;
- подытожим, что каждый проход имеет (всего значений в массиве, конкретное число) минус (номер прохода) сравнений.
Еще короче алгоритм будущей программы можно записать так:
- массив чисел проверяется до тех пор, пока не будут найдены какие-либо два числа, причем второе из них обязано быть больше первого;
- неправильно расположенные по отношению друг к другу элементы массива программа меняет местами.
Псевдокод на основе описанного алгоритма
Самая простая реализация выполняется так:
Процедура Sortirovka_Puzirkom ;
Начало
цикл для j от nachalnii_index до konechii_index ;
цикл для i от nachalnii_index до konechii_index-1 ;
если massiv[i]>massiv
(меняем значения местами);
Конец
Конечно, здесь простота только усугубляет ситуацию: чем проще алгоритм, тем более в нем проявляются все недостатки. Затратность времени слишком велика даже для небольшого массива (тут вступает в дело относительность: для обывателя количество времени может казаться маленьким, но в деле программиста каждая секунда или даже миллисекунда на счету).
Потребовалась реализация получше. Например, учитывающая обмен значений в массиве местами:
Процедура Sortirovka_Puzirkom ;
Начало
sortirovka = истина;
цикл пока sortirovka = истина;
sortirovka = ложь;
цикл для i от nachalnii_index до konechii_index-1 ;
если massiv[i]>massiv (первый элемент больше второго), то:
(меняем элементы местами);
sortirovka = истина; (обозначили, что обмен был произведен).
Конец.
Недостатки метода
Основной минус - продолжительность процесса. Сколько же времени выполняется пузырьком?
Время выполнения рассчитывается из квадрата количества чисел в массиве - конечный результат ему пропорционален.
При наихудшем варианте массив будет пройден столько же раз, сколько в нем имеется элементов минус одно значение. Так происходит потому, что в конечном итоге остается только один элемент, который не с чем сравнивать, и последний проход по массиву становится бесполезным действом.
Кроме того, эффективен метод сортировки простыми обменами, как его еще называют, только для массивов небольшого размера. Большие объемы данных с его помощью обработать не получится: результатом станут либо ошибки, либо сбой работы программы.
Достоинства
Сортировка пузырьком весьма проста для понимания. В учебных программах технических ВУЗов при изучении упорядочивания элементов массива ее проходят в первую очередь. Метод легко реализуется как на языке программирования Delphi (Д (Делфи), так и на C/C++ (Си/Си плюс плюс), невероятно простой алгоритм расположения значений в верном порядке и на Сортировка пузырьком идеально подходит для начинающих.
По причине недостатков алгоритм не применяют во внеучебных целях.
Наглядный принцип сортировки
Изначальный вид массива 8 22 4 74 44 37 1 7
Шаг 1 8 22 4 74 44 37 1 7
8 22 4 74 44 1 37 7
8 22 4 74 1 44 37 7
8 22 4 1 74 44 37 7
8 22 1 4 74 44 37 7
8 1 22 4 74 44 37 7
1 8 22 4 74 44 37 7
Шаг 2 1 8 22 4 74 44 7 37
1 8 22 4 74 7 44 37
1 8 22 4 7 74 44 37
1 8 22 4 7 74 44 37
1 8 4 22 7 74 44 37
1 4 8 22 7 74 44 37
Шаг 3 1 4 8 22 7 74 37 44
1 4 8 22 7 37 74 44
1 4 8 22 7 37 74 44
1 4 8 7 22 37 74 44
1 4 7 8 22 37 74 44
Шаг 4 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Шаг 5 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Шаг 6 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Шаг 7 1 4 7 8 22 37 44 74
Пример сортировки пузырьком на языке Pascal
Пример:
const kol_mas=10;
var massiv:array of integer;
a, b, k: integer;
writeln ("input", kol_mas, "elements of array");
for a:=1 to kol_mas do readln(massiv[a]);
for a:=1 to kol_mas-1 do begin
for b:=a+1 to kol_mas do begin
if massiv[a]>massiv[b] then begin
k:=massiv[a]; massiv[a]:=massiv[b]; massiv[b]:=k;
end;
writeln ("after sort");
for a:=1 to kol_mas do writeln(massiv[a]);
Пример сортировки пузырьком на языке С (Си)
#include
#include
int main(int argc, char* argv)
int massiv = {36, 697, 73, 82, 68, 12, 183, 88},i, ff;
for (; ;){
ff = 0;
for (i = 7; i>0; i--){
if (massiv[i] < massiv) {
swap (massiv[i],massiv);
if (ff == 0) break;
getch(); // задержка экрана
Сортировка пузырьком – простейший алгоритм сортировки, применяемый чисто для учебных целей. Практического применения этому алгоритму нет, так как он не эффективен, особенно если необходимо отсортировать массив большого размера. К плюсам сортировки пузырьком относится простота реализации алгоритма.
Алгоритм сортировки пузырьком сводится к повторению проходов по элементам сортируемого массива. Проход по элементам массива выполняет внутренний цикл. За каждый проход сравниваются два соседних элемента, и если порядок неверный элементы меняются местами. Внешний цикл будет работать до тех пор, пока массив не будет отсортирован. Таким образом внешний цикл контролирует количество срабатываний внутреннего цикла Когда при очередном проходе по элементам массива не будет совершено ни одной перестановки, то массив будет считаться отсортированным. Чтобы хорошо понять алгоритм, отсортируем методом пузырька массив, к примеру, из 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 — Сортировка пузырьком
Всем привет!
Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык 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.
Вот результат:
А вот видеоурок
Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.
Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.
Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.
В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.
В этой статье приведены примеры реализации стандартных алгоритмов сортировки.
Сортировка выбором (Selection sort)
Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в надлежащем порядке.
Код C++
void
SortAlgo::selectionSort(int
data, int
lenD)
{
int
j = 0;
int
tmp = 0;
for
(int
i=0; i
Пузырьковая сортировка (Bubble sort)
При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время первого прохода сраваются первые два элемента в массиве. Если они не в порядке, они меняются местами и затем сравнивается элементы в следующей паре. При том же условии они так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет достигнут конец массива.
Код C++
void
SortAlgo::bubbleSort(int
data, int
lenD)
{
int
tmp = 0;
for
(int
i = 0;i При сортировке вставками массив разбивается на две области: упорядоченную и
и неупорядоченную. Изначально весь массив является неупорядоченной областью.
При первом проходе первый элемент из неупорядоченной области изымается и помещается
в правильном положении в упорядоченной области. На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной
области сокращается на 1. Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в
правильное положение в упорядоченной области. Это сделано путем сдвига всех
элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i]
вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i]. Код C++
void
SortAlgo::insertionSort(int
data, int
lenD)
{
int
key = 0;
int
i = 0;
for
(int
j = 1;j Код C++
void
SortAlgo::mergeSort(int
data, int
lenD)
{
if
(lenD>1){
int
middle = lenD/2;
int
rem = lenD-middle;
int
* L = new int
;
int
* R = new int
;
for
(int
i=0;i Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения
исходного массива на две области. Эти части находятся слева и справа от отмеченного
элемента, называемого опорным. В конце процесса одна часть будет
содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше
опорного. Код C++
void
SortAlgo::quickSort(int
* data, int const
len)
{
int const
lenD = len;
int
pivot = 0;
int
ind = lenD/2;
int
i,j = 0,k = 0;
if
(lenD>1){
int
* L = new int
;
int
* R = new int
;
pivot = data;
for
(i=0;i Алгоритм сортировки одномерного
массива методом «пузырька». Описание
алгоритма. Блок-схема и программа
сортировки по возрастанию массива типа
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);Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
Пример сортировки методом пузырька
Сортировка методом пузырька
,
,
,
.Блок–схема сортировки методом пузырька.
Антивирус Bitdefender: эффективный защитник Без вопросов
Значение слова неудачный
Обзор Samsung Galaxy A7 (2017): не боится воды и экономии Стоит ли покупать samsung a7
Делаем бэкап прошивки на андроиде
Как настроить файл подкачки?