Сортировка массива c методом пузырька. Сортировка методом пузырька

Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.

Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.

Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.

В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.

В этой статье приведены примеры реализации стандартных алгоритмов сортировки.

Сортировка выбором (Selection sort)

Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в надлежащем порядке.

Код C++

void SortAlgo::selectionSort(int data, int lenD) { int j = 0; int tmp = 0; for (int i=0; idata[k]){ j = k; } } tmp = data[i]; data[i] = data[j]; data[j] = tmp; } }

Пузырьковая сортировка (Bubble sort)

При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время первого прохода сраваются первые два элемента в массиве. Если они не в порядке, они меняются местами и затем сравнивается элементы в следующей паре. При том же условии они так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет достигнут конец массива.

Код C++

void SortAlgo::bubbleSort(int data, int lenD) { int tmp = 0; for (int i = 0;i=(i+1);j--){ if (data[j]

Сортировка вставками (Insertion sort)

При сортировке вставками массив разбивается на две области: упорядоченную и и неупорядоченную. Изначально весь массив является неупорядоченной областью. При первом проходе первый элемент из неупорядоченной области изымается и помещается в правильном положении в упорядоченной области.

На каждом проходе размер упорядоченной области возрастает на 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=0 && data[i]>key){ data = data[i]; i = i-1; data=key; } } }

Сортировка слиянием (Merge sort)

Код 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

Быстрая сортировка (Quick sort)

Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения исходного массива на две области. Эти части находятся слева и справа от отмеченного элемента, называемого опорным. В конце процесса одна часть будет содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше опорного.

Код 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

Сегодня мы затронем тему сортировки в Паскале. Есть достаточно много различных методов, большинство из них не имеет широкой известности, да и знание их в принципе и не нужно. Достаточно знать базовый набор и несколько дополнительных. В этой статья я расскажу вам о самой известной сортировке - это сортировка методом пузырька, которую также называют сортировкой простого обмена.
Для начала, что такое сортировка в паскале и зачем она нужна? Сортировка - это метод упорядочить массив (обычно по возрастанию или убыванию) . В задачах встречаются такие строки "расположить элементы массива, начиная от минимального (максимального)" . Имейте ввиду, что это то же самое.
Вернемся к сортировке пузырьком. Почему ее назвали именно так? Дело в том, что это аналогия. Представьте себе обычный массив, расположенный вертикально. В результате сортировки более меньшие элементы поднимаются вверх. То есть здесь массив можно представить в виде воды, а меньшие элементы в виде пузырька, которые всплывают наверх.

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 . Он нужен только для одной цели: чтобы поменять два элемента массива местами. Дело в том, что в Паскале нет специальной функции, которая бы выполняла такое действие. Поэтому приходится расписывать ее самому, добавляя дополнительный элемент для обмена. На этом статья сортировка методом пузырька закончена, следующие статьи выйдут в течении следующей недели (а может и раньше).

Не только не считается самым быстрым методом, более того, она замыкает перечень самых медленных способов упорядочивания. Однако и у нее есть свои плюсы. Так, сортировка методом пузырька - самое что ни на есть логичное и естественное решение проблемы, если необходимо расставить элементы в определенном порядке. Обычный человек вручную, к примеру, воспользуется именно им - просто по интуиции.

Откуда взялось такое необычное название?

Название метода придумали, используя аналогию с воздушными пузырьками в воде. Это метафора. Подобно тому, как маленькие пузыри воздуха поднимаются наверх - ведь их плотность больше, чем какой-либо жидкости (в данном случае - воды), так и каждый элемент массива, чем меньше он по значению, тем больше он постепенно пробирается к началу перечня чисел.

Описание алгоритма

Сортировка пузырьком выполняется следующим образом:

• первый проход: элементы массива чисел берутся по два и также парами сравниваются. Если в какой-то двойке элементов первое значение оказывается больше второго, программа производит их обмен местами;
• следовательно, попадает в конец массива. В то время как все остальные элементы остаются, как и были, в хаотичном порядке и требуют еще сортировки;
• поэтому и необходим второй проход: производится он по аналогии с предыдущим (уже описанным) и имеет число сравнений - минус один;
• у прохода номер три сравнений на единицу меньше, чем у второго, и на двойку, чем у первого. И так далее;
• подытожим, что каждый проход имеет (всего значений в массиве, конкретное число) минус (номер прохода) сравнений.

Еще короче алгоритм будущей программы можно записать так:

• массив чисел проверяется до тех пор, пока не будут найдены какие-либо два числа, причем второе из них обязано быть больше первого;
• неправильно расположенные по отношению друг к другу элементы массива программа меняет местами.

Псевдокод на основе описанного алгоритма

Самая простая реализация выполняется так:

Процедура 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(); // задержка экрана

При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания . Это значит, что элементы того же массива нужно расположить строго по порядку. Например, в случае сортировки по возрастанию предшествующий элемент должен быть меньше последующего (или равен ему).

Решение

Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька , который также называют методом простого обмена . В чем же он заключается, и почему у него такое странное название: "метод пузырька"?

Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

Алгоритм и особенности этой сортировки таковы:

1. При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
2. Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
3. При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
4. На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
5. В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
6. После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.
7. Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
8. При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.

Программа на языке Паскаль:

const m = 10 ; var arr: array [ 1 .. m ] of integer ; i, j, k: integer ; begin randomize; write ("Исходный массив: " ) ; for i : = 1 to m do begin arr[ i] : = random(256 ) ; write (arr[ i] : 4 ) ; end ; writeln ; writeln ; for i : = 1 to m- 1 do for j : = 1 to m- i do if arr[ j] > arr[ j+ 1 ] then begin k : = arr[ j] ; arr[ j] : = arr[ j+ 1 ] ; arr[ j+ 1 ] : = k end ; write ("Отсортированный массив: " ) ; for i : = 1 to m do write (arr[ i] : 4 ) ; writeln ; readln end .

Алгоритм сортировки одномерного массива методом «пузырька». Описание алгоритма. Блок-схема и программа сортировки по возрастанию массива типа real из 7 элементов.

Описание алгоритма

Классификация методов сортировки не всегда четко определена. Остановимся на методе, в котором обмен двух элементов является основной характеристикой процесса. Приведенный ниже алгоритм сортировки простым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы.

Как и в предыдущих методах простого выбора, мы совершаем повторные проходы по массиву, каждый раз просеивая наименьший элемент оставшегося множества, двигаясь к левому концу массива. Если, для разнообразия, мы будем рассматривать массив, расположенный вертикально, а не горизонтально и – при помощи некоторого воображения - представим себе элементы пузырьками в резервуаре с водой, обладающими «весами», соответствующими их ключам, то каждый проход по массиву приводит к «всплыванию» пузырька на соответствующий его весу уровень (см. табл. 2). Этот метод широко известен как сортировка методом пузырька . Его простейший вариант приведен в программе 1.

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 }

1. Сортировка методом пузырька

Этот алгоритм легко оптимизировать. Пример в табл. 2 показывает, что три последних прохода никак не влияют на порядок элементов, поскольку те уже рассортированы. Очевидный способ улучшить данный алгоритм – это запоминать, производился ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм можно продолжить, если запоминать не только сам факт обмена, но и место (индекс) последнего обмена. Ведь ясно, что все пары соседних элементов с индексами, меньшими этого индекса k , уже расположены в нужном порядке. Поэтому следующие проходы можно заканчивать на этом индексе, вместо того чтобы двигаться до установленной заранее нижней границыi . Однако внимательный программист заметит здесь странную асимметрию: один неправильно расположенный «пузырек» в «тяжелом» конце рассортированного массива всплывает на место за один проход, а неправильно расположенный элемент в «легком» конце будет опускаться на правильное место только на один шаг на каждом проходе. Например, массив

12 18 42 44 55 67 94 06

будет рассортирован при помощи метода пузырька за один проход, а сортировка массива

94 06 12 18 42 44 55 67

потребует семи проходов. Эта неестественная асимметрия подсказывает третье улучшение: менять направление следующих один за другим проходов.

Анализ сортировки методом пузырька.

Число сравнений в алгоритме простого обмена равно

,

минимальное, среднее и максимальное количества пересылок (присваиваний элементов) равны

,

,

.

1. Блок–схема сортировки методом пузырька.

Программа сортировки

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);