Читайте также:
|
Просматривается каждая пара соседних элементов в совокупности: аj и аj+1 для j =0,1,…n-2. Если элементы пары не находятся в нужном отношении, т.е.: аj > аj+1 , то они переставляются (меняются местами).
Схема алгоритма:
for (int j=0; j<n-1;j++) if (a [j] > a [j+1]){ < a [j] Û a [j+1] };
Назовём такой просмотр просмотром «Слева направо» (Þ), а просмотр
for (int j=n-2; j>=0;j--) if (a [j] > a [j+1]) { < a [j] Û a [j+1] }; назовем просмотром Справа налево» (Ü).
Элементы совокупности ассоциируются с пузырьками воздуха в чане с водой: каждый пузырёк со своим весом-значением. Отсюда и название метода пузырьковая сортировка.
Можно отметить, что
¨ за один просмотр элементы, вообще говоря, не будут упорядочены;
¨ однако, если во время просмотра не было ни одной перестановки, то совокупность упорядочена; можно сделать вывод, что просмотры необходимо повторять, пока есть перестановки;
¨ за один просмотр самый тяжелый пузырёк встанет на свое место, поэтому в следующем просмотре его можно не трогать, т.е.в следующих просмотрах уменьшается количество просматриваемых пар;
¨ за один просмотр самый легкий пузырёк продвинется к своему месту на одну позицию, т.е. если самый легкий пузырек стоял на дне (худший случай), то за (n -1) просмотр он встанет на свое место; отсюда вывод: за (n-1) просмотр совокупность будет упорядочена.
//пузырьковая сортировка
void bubble (int a[], int n)
{for (int i=0;i<n-1;i++) // n-1 просмотр
for (int j=n-1;j>i;j--) // Просмотры «справа налево» (Ü).
if (a[j-1] > a[j]) {int r = a[j-1]; a[j-1]= a[j]; a[j]=r;}
}
Характеристики алгоритма сортировки с помощью прямого Обмена:
Порядок метода О(n2)
Модификации прямого Обмена:
1. Модификация. Можно выполнять просмотры «Слева направо» (Þ)
//пузырьковая сортировка1
void bubble1 (int a[ ], int n)
{for (int i=n-1;i>0;i--) // n-1 просмотр
for (int j=0; j<i;j++) // пока j<i, т.к. тяжелый ->на свое место
if (a[j ] > a[j+1]) {int r = a[j]; a[j]= a[j+1]; a[j+1]=r;}
}
2. Модификация. Запоминание факта перестановки. Недостатком прямого обмена является выполнение (n-1) просмотра даже в случае, если совокупность упорядочится раньше (также в случае заданной упорядоченной совокупности). Удобно организовать проверку, были ли перестановки элементов во время просмотра и, если не было (т.е. совокупность упорядочена), прекратить просмотры.
Схема алгоритма:
i:= 0; p:= true;
While (p) //{пока есть перестановки}
{i:= i + 1; //{номер просмотра}
p:= f a lse;
for (int j=0; j<n-i; j++) if (a [j] > a [j+1]) {int R:= a [j]; a [j]:= a [j+1]; a [j+1]:=R;
p:= true //запоминание факта перестановки
}
}
Дата добавления: 2014-12-20; просмотров: 72 | Поможем написать вашу работу | Нарушение авторских прав |