Сортировка пузырьком (bubble sort) — один из самых простых для понимания методов сортировки.
Алгоритм выполняет повторяющиеся проходы по массиву. Во время каждого прохода сортируемые элементы попарно сравниваются, и если порядок в паре неверный, элементы меняются местами (отсюда второе название — сортировка простыми обменами).
Визуализация алгоритма сортировки пузырьком
Реализация алгоритма
program BubbleSort; const arrayLength = 10; var inputArray : array [1..arrayLength] of integer; i, j, tempValue: integer; begin randomize; writeln (‘Исходный массив: ‘); for i := 1 to arrayLength do begin inputArray[i] := random(100); write (inputArray[i]:4); end; writeln; for i := 1 to arrayLength-1 do for j := 1 to arrayLength-i do if inputArray[j] > inputArray[j+1] then begin tempValue := inputArray[j]; inputArray[j] := inputArray[j+1]; inputArray[j+1] := tempValue; end; writeln (‘Отсортированный массив: ‘); for i := 1 to arrayLength do write (inputArray[i]:4); readln; end.
Результат работы программы:
Паскаль с нуля [ч12]. Сортировка массива методом пузырька
В приведенной программе производиться сортировка по возрастанию, для сортировки по убыванию достаточно изменить операцию сравнения в строке if inputArray[j] > inputArray[j+1] then , с больше — “>” на меньше — “
Источник: programm.top
Сортировка пузырьком
Сортировка пузырьком – простейший алгоритм сортировки, применяемый чисто для учебных целей. Практического применения этому алгоритму нет, так как он не эффективен, особенно если необходимо отсортировать массив большого размера. К плюсам сортировки пузырьком относится простота реализации алгоритма.
Алгоритм сортировки пузырьком сводится к повторению проходов по элементам сортируемого массива. Проход по элементам массива выполняет внутренний цикл. За каждый проход сравниваются два соседних элемента, и если порядок неверный элементы меняются местами. Внешний цикл будет работать до тех пор, пока массив не будет отсортирован.
Таким образом внешний цикл контролирует количество срабатываний внутреннего цикла Когда при очередном проходе по элементам массива не будет совершено ни одной перестановки, то массив будет считаться отсортированным. Чтобы хорошо понять алгоритм, отсортируем методом пузырька массив, к примеру, из 7 чисел (см. Таблица 1).
исходный массив: 3 3 7 1 2 5 0
| исх. массив | 3 | 3 | 7 | 1 | 2 | 5 | ||
| 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 | 7 | 7>0, true | ||||||
| тек. массив | 3 | 3 | 1 | 2 | 5 | 7 | ||
| 3 | 3 | false | ||||||
| 1 | 1 | 3 | 3>1, true | |||||
| 2 | 2 | 3 | 3>2, true | |||||
| 3 | 3 | 3>0, true | ||||||
| 4 | 3 | 5 | false | |||||
| 5 | 5 | 7 | false | |||||
| тек. массив | 3 | 1 | 2 | 3 | 5 | 7 | ||
| 1 | 3 | 3>1, true | ||||||
| 1 | 2 | 3 | 3>2, true | |||||
| 2 | 3 | 3>0, true | ||||||
| 3 | 3 | 3 | false | |||||
| 4 | 3 | 5 | false | |||||
| 5 | 5 | 7 | false | |||||
| тек. массив | 1 | 2 | 3 | 3 | 5 | 7 | ||
| 1 | 2 | false | ||||||
| 2 | 2>0, true | |||||||
| 2 | 3 | false | ||||||
| 3 | 3 | false | ||||||
| 3 | 5 | false | ||||||
| 5 | 7 | false | ||||||
| тек. массив | 1 | 2 | 3 | 3 | 5 | 7 | ||
| 1 | 1>0, true | |||||||
| 1 | 2 | false | ||||||
| 2 | 3 | false | ||||||
| 3 | 3 | false | ||||||
| 3 | 5 | false | ||||||
| 5 | 7 | false | ||||||
| конечный массив | 1 | 2 | 3 | 3 | 5 | 7 | ||
| Конец сортировки | ||||||||
Для того чтобы отсортировать массив хватило пяти запусков внутреннего цикла, for . Запустившись, цикл for срабатывал 6 раз, так как элементов в массиве 7, то итераций (повторений) цикла for должно быть на одно меньше. На каждой итерации сравниваются два соседних элемента массива. Если текущий элемент массива больше следующего, то меняем их местами.
Таким образом, пока массив не будет отсортирован, будет запускаться внутренний цикл и выполняться операция сравнения. Обратите внимание на то, что за каждое полное выполнение цикла for как минимум один элемент массива находит своё место. В худшем случае, понадобится n-2 запуска внутреннего цикла, где n – количество элементов массива. Это говорит о том, что сортировка пузырьком крайне не эффективна для больших массивов.
Разработаем программу, в которой сначала необходимо ввести размер одномерного массива, после чего массив заполняется случайными числами и сортируется методом пузырька.
// bu_sort.cpp: определяет точку входа для консольного приложения. #include «stdafx.h» #include #include #include using namespace std; void bubbleSort(int *, int); // прототип функции сортировки пузырьком int main(int argc, char* argv[]) < srand(time(NULL)); setlocale(LC_ALL, «rus»); cout > size_array; int *sorted_array = new int [size_array]; // одномерный динамический массив for (int counter = 0; counter < size_array; counter++) < sorted_array[counter] = rand() % 100; // заполняем массив случайными числами cout cout cout void bubbleSort(int* arrayPtr, int length_array) // сортировка пузырьком < int temp = 0; // временная переменная для хранения элемента массива bool exit = false; // болевая переменная для выхода из цикла, если массив отсортирован while (!exit) // пока массив не отсортирован < exit = true; for (int int_counter = 0; int_counter < (length_array — 1); int_counter++) // внутренний цикл //сортировка пузырьком по возрастанию — знак >//сортировка пузырьком по убыванию — знак < if (arrayPtr[int_counter] >arrayPtr[int_counter + 1]) // сравниваем два соседних элемента < // выполняем перестановку элементов массива temp = arrayPtr[int_counter]; arrayPtr[int_counter] = arrayPtr[int_counter + 1]; arrayPtr[int_counter + 1] = temp; exit = false; // на очередной итерации была произведена перестановка элементов >> >
Результат работы программы показан на рисунке 1.
Рисунок 1 — Сортировка пузырьком
Источник: cppstudio.com
Установите порядок работы программы сортировка методом пузырька
- Вы здесь:
- Главная
- Видеотека
- Программирование и сеть
- Алгоритмы и структуры данных
- Сортировка и поиск
- Пузырьковая сортировка (Bubble-sort)
Пузырьковая сортировка (Bubble-sort)
Подробности Категория: Сортировка и поиск
Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Пример работы алгоритма
Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами. (1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 
(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (
), алгоритм не меняет их местами.
(1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)
Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
(1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)
Теперь массив отсортирован и алгоритм может быть завершён.
Реализация алгоритма на различных языках программирования:
Синтаксис Intel
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[di] mov byte ptr bx[di], al mov byte ptr bx[si], ah no_swap: inc dx jmp for_j exit_for_j: loop for_i
Синтаксис AT 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[j + 1]) SWAP( a[j], a[j + 1] ); > > >
C++
С использованием Template
#include template < typename Iterator >void bubble_sort( Iterator First, Iterator Last )
Без использования Template
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[j+1]) < int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; >> > >
C#
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; >> > >
Delphi
Сортировка одномерного динамического целочисленного массива:
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[i+1] then begin p:= a[i]; a[i]:= a[i+1]; a[i+1]:= p; b:= true; end; until not b; end;
D
void bubbleSort(alias op, T)(T[] inArray) < foreach (i, ref a; inArray) < foreach (ref b; inArray[i+1..$]) < if (mixin(op)) < auto tmp = a; a = b; b = tmp; >> > >
Fortran
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
Java
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; >> > >
Pascal
for i:=n-1 downto 1 do for j:=1 to i do if M[j]>M[j+1] then begin tmp:= M[j]; M[j]:= M[j+1]; M[j+1]:= 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[i+1] Then Begin A:=X[i]; X[i]:=X[i+1]; X[i+1]:=A; P:=true; End; k:=k+1; End;
Perl
Ruby
arr = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10] swap = true size = arr.length — 1 while swap swap = false for i in 0. size swap |= arr[i] > arr[i + 1] arr[i], arr[i+1] = arr[i + 1], arr[i] if arr[i] > arr[i + 1] end size -= 1 end puts arr.join(‘ ‘) # output => 1 3 3 5 8 10 11 12 17 20
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 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
PHP
$size = sizeof($arr)-1; for ($i = $size; $i>=0; $i—) < for ($j = 0; $j$arr[$j+1]) < $k = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $k; >>
JavaScript
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[j+1]) < tmp = data[j]; data[j] = data[j+1]; data[j+1] = tmp; >> > return data; >
JavaFX
function bubbleSort(seq:Number[]):Number[] < var sort = seq; var elem:Number; for(n in reverse [0..sizeof seq — 2])< for(i in [0..n] )< if(sort[i+1] < sort[i] )< elem = sort[i]; sort[i] = sort[i+1]; sort[i+1] = elem; >> > return sort; >
Nemerle
using System.Console; using Nemerle.Collections; def arr = array [100, 45, 2, 5, 3, 122, 3, 5, 6, 1, 3]; foreach (i in [0..arr.Length-1]) foreach (j in [0..arr.Length-2]) when (arr[j] > arr[j+1]) (arr[j], arr[j+1]) = (arr[j+1], arr[j]); WriteLine($»Sorted list is a $(arr.ToList())»);
TurboBasic 1.1
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[XS] Y[XS]=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[I+1] THEN D=Y[I]:Y[I]=Y[I+1]:Y[I+1]=D:F=1 IF Y[I] > Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1 LOCATE 8,1 REM PRINT » ANYMACIJA SORTIROVKI» REM FOR X1=1 TO N REM ANIMATION BLOCK PRINT Y[X1]; 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 font-family: comic sans ms,sans-serif; font-size: 14pt;»>Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).
Источник: forkettle.ru