Пузырьковая сортировка и все-все-все. Сортировка пузырьком Пузырьковый алгоритм
Метод пузырька
Сортировка простыми обменами , сортиро́вка пузырько́м (англ. bubble sort ) - простой алгоритм сортировки . Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n ²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками .
Алгоритм
Пример сортировки пузырьком списка случайных чисел.
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Иногда на каждом шаге массив просматривается то с начала, то с конца. Это называется шейкерная сортировка .
Примеры реализации
Python
Def swap(arr, i, j) : arr[ i] , arr[ j] = arr[ j] , arr[ i] def bubble_sort(arr) : i = len (arr) while i > 1 : for j in xrange (i - 1 ) : if arr[ j] > arr[ j + 1 ] : swap(arr, j, j + 1 ) i -= 1
VBA
Sub Sort(Mus() As Long ) Dim n As Long , i As Long , tmp As Long i = 1 Do While (i < UBound (Mus) ) If Mus(i) > Mus(i + 1 ) Then tmp = Mus(i) Mus(i) = Mus(i + 1 ) Mus(i + 1 ) = tmp If i > 1 Then i = i - 1 Else i = i + 1 End If Else i = i + 1 End If Loop End Sub
Усовершенствованный алгоритм сортировки пузырьком в Pascal
P:=True ; {Перестановка есть} K:=1 ; {Номер просмотра} While P Do Begin P:=false ; For i:=1 To n-k Do If X[ i] > X[ i+1 ] Then Begin A:=X[ i] ; X[ i] :=X[ i+1 ] ; X[ i+1 ] :=A; P:=true ; End ; k:=k+1 ; End ;
PHP
$size = count ($arr ) -1 ; for ($i = $size ; $i >=0 ; $i --) { for ($j = 0 ; $j <=($i -1 ) ; $j ++) if ($arr [ $j ] >$arr [ $j +1 ] ) { $k = $arr [ $j ] ; $arr [ $j ] = $arr [ $j +1 ] ; $arr [ $j +1 ] = $k ; } }
Сортировка пузырьком – простейший алгоритм сортировки, применяемый чисто для учебных целей. Практического применения этому алгоритму нет, так как он не эффективен, особенно если необходимо отсортировать массив большого размера. К плюсам сортировки пузырьком относится простота реализации алгоритма.
Алгоритм сортировки пузырьком сводится к повторению проходов по элементам сортируемого массива. Проход по элементам массива выполняет внутренний цикл. За каждый проход сравниваются два соседних элемента, и если порядок неверный элементы меняются местами. Внешний цикл будет работать до тех пор, пока массив не будет отсортирован. Таким образом внешний цикл контролирует количество срабатываний внутреннего цикла Когда при очередном проходе по элементам массива не будет совершено ни одной перестановки, то массив будет считаться отсортированным. Чтобы хорошо понять алгоритм, отсортируем методом пузырька массив, к примеру, из 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.
Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.
Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.
Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.
В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.
В этой статье приведены примеры реализации стандартных алгоритмов сортировки.
Сортировка выбором (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 Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
Второй проход:
Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
Третий проход:
Теперь массив отсортирован и алгоритм может быть завершён.
Реализация алгоритма на различных языках программирования:
Mov bx, offset array
mov cx, n
for_i:
dec cx
xor dx, dx
for_j:
cmp dx, cx
jae exit_for_j
jbe no_swap
mov ah, byte ptr bx
mov byte ptr bx, al
mov byte ptr bx, ah
no_swap:
inc dx
jmp for_j
exit_for_j:
loop for_i Text
# void bubble_sort (unsigned *array, unsigned length);
.globl bubble_sort
.type bubble_sort, @function
bubble_sort:
mov 8(%esp), %ecx # unsigned length
cmp $1, %ecx
jbe exit
mov 4(%esp), %eax # unsigned *array
dec %ecx
for_ecx:
xor %edi, %edi
for_edi:
mov (%eax,%edi,4), %ebx
cmp %ebx, 4(%eax,%edi,4)
jae no_xchng
mov 4(%eax,%edi,4), %edx
mov %edx, (%eax,%edi,4)
mov %ebx, 4(%eax,%edi,4)
no_xchng:
inc %edi
cmp %edi, %ecx
jne for_edi
loop for_ecx
exit:
ret
#define SWAP(A, B) { int t = A; A = B; B = t; }
void bubblesort(int *a, int n)
{
int i, j;
for (i = n - 1; i > 0; i--)
{
for (j = 0; j < i; j++)
{
if (a[j] > a)
SWAP(a[j], a);
}
}
}
#include Void bubble(int* a, int n)
{
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j < i; j++)
{
if (a[j] > a)
{
int tmp = a[j];
a[j] = a;
a = tmp;
}
}
}
}
Void BubbleSort(int A)
{
for (int i = 0; i < A.Length; i++)
{
for (int j = i+1; j < A.Length; j++)
{
if (A[j] < A[i])
{
var temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
}
Сортировка одномерного динамического целочисленного массива: Type
TIntVec = array of Integer;
...
procedure BubbleSort(var a: TIntVec);
var i,p,n: Integer; b: boolean;
begin
n:= Length(a);
if n < 2 then exit;
repeat
b:= false;
Dec(n);
if n > 0 then
for i:= 0 to n-1 do
if a[i] > a then
begin
p:= a[i];
a[i]:= a;
a:= p;
b:= true;
end;
until not b;
end;
Void bubbleSort(alias op, T)(T inArray) {
foreach (i, ref a; inArray) {
foreach (ref b; inArray) {
if (mixin(op)) {
auto tmp = a;
a = b;
b = tmp;
}
}
}
}
Do i=n-1,1,-1
do j=1,i
if (a(j).gt.a(j+1)) then
t=a(j)
a(j)=a(j+1)
a(j+1)=t
endif
enddo
enddo
Void bubblesort(int arr) {
for (int i = 0; i < arr.length-1; i++){
for (int j = i+1; j < arr.length; j++){
if (arr[i] < arr[j]) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
}
}
For i:=n-1 downto 1 do {n - размер массива M}
for j:=1 to i do
if M[j]>M then
begin
tmp:= M[j];
M[j]:= M;
M:= tmp;
end;
write("вывод значений M: ");
for i:=1 to n do
write(M[i]:4);
writeln;
Усовершенствованный алгоритм сортировки пузырьком: P:=True; {есть перестановка?}
K:=1; {Номер просмотра}
While P Do
Begin
P:=false;
For i:=1 To n-k Do
If X[i] > X Then
Begin
A:=X[i];
X[i]:=X;
X:=A;
P:=true;
End;
k:=k+1;
End;
For(@out){
for(0..$N-1){
if($out[$_]gt$out[$_+1]){
($out[$_],$out[$_+1])=($out[$_+1],$out[$_]);
}
}
}
Arr =
swap = true
size = arr.length - 1
while swap
swap = false
for i in 0...size
swap |= arr[i] > arr
arr[i], arr = arr, arr[i] if arr[i] > arr
end
size -= 1
end
puts arr.join(" ")
# output => 1 3 3 5 8 10 11 12 17 20
Def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def bubble_sort(arr):
i = len(arr)
while i > 1:
for j in xrange(i - 1):
if arr[j] > arr:
swap(arr, j, j + 1)
i -= 1
Sub Sort(Mus() As Long)
Dim i As Long, tmp As Long, t As Boolean
t = True
Do While t
t = False
For i = 0 To UBound(Mus()) - 1
If Mus(i) > Mus(i + 1) Then
tmp = Mus(i)
Mus(i) = Mus(i + 1)
Mus(i + 1) = tmp
t = True
End If
Next
Loop
End Sub
$size = sizeof($arr)-1;
for ($i = $size; $i>=0; $i--) {
for ($j = 0; $j<=($i-1); $j++)
if ($arr[$j]>$arr[$j+1]) {
$k = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $k;
}
}
Function sortBubble(data) {
var tmp;
for (var i = data.length - 1; i > 0; i--) {
for (var j = 0; j < i; j++) {
if (data[j] > data) {
tmp = data[j];
data[j] = data;
data = tmp;
}
}
}
return data;
}
Function bubbleSort(seq:Number):Number{
var sort = seq;
var elem:Number;
for(n in reverse ){
for(i in ){
if(sort < sort[i]){
elem = sort[i];
sort[i] = sort;
sort = elem;
}
}
}
return sort;
}
Using System.Console;
using Nemerle.Collections;
def arr = array ;
foreach (i in )
foreach (j in )
when (arr[j] > arr)
(arr[j], arr) = (arr, arr[j]);
WriteLine($"Sorted list is a $(arr.ToList())");
CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 " 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] "FRE(-1)=21440-21456
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
FOR X = 1 TO N
Y[X] = X
PRINT Y[X];
NEXT X:PRINT
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
PRINT " SLUCHAINYE CHISLA"
FOR X = 1 TO N
YD=Y[X]
XS=INT(RND*N)+1
PRINT XS;
Y[X]=Y
Y=YD
NEXT X:PRINT
PRINT " PEREMESHANNYJ MASSIV"
FOR X=1 TO N
PRINT Y[X];
NEXT X:PRINT
"ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2)
MTIMER
FOR J=1 TO N-1 STEP 1
F=0
FOR I=1 TO N-J STEP 1
"IF Y[I] > Y THEN D=Y[I]:Y[I]=Y:Y=D:F=1
IF Y[I] > Y THEN SWAP Y[I],Y:F=1
LOCATE 8,1 REM
PRINT " ANYMACIJA SORTIROVKI" REM
FOR X1=1 TO N REM ANIMATION BLOCK
PRINT Y; REM
NEXT X1:PRINT REM
DELAY .5 REM
NEXT I
IF F=0 THEN EXIT FOR
NEXT J
T1=MTIMER
PRINT " OTSORTIROVANNYJ MASSIV"
FOR X=1 TO N
PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1
Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).
При написании статьи были использованы открытые источники сети интернет:
При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания
. Это значит, что элементы того же массива нужно расположить строго по порядку. Например, в случае сортировки по возрастанию предшествующий элемент должен быть меньше последующего (или равен ему). Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька
, который также называют методом простого обмена
. В чем же он заключается, и почему у него такое странное название: "метод пузырька"? Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива). Программа на языке Паскаль: 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
.
Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
Худшее время
Лучшее время
Среднее время
Затраты памяти
Пример работы алгоритма
Синтаксис Intel
Синтаксис AT&T (GNU)
C
C++
С использованием Template
Без использования Template
C#
Delphi
D
Fortran
Java
Pascal
Perl
Ruby
Python
VBA
PHP
JavaScript
JavaFX
Nemerle
TurboBasic 1.1
Решение
Алгоритм и особенности этой сортировки таковы:
