Сортировка пузырьком — это самый простой алгоритм сортировки, который работает путем многократной замены соседних элементов, если они находятся в неправильном порядке.
( 5 1 4 2 8) ( 1 5 4 2 8), здесь алгоритм сравнивает два первых элемента и меняет их местами, так как (5>1).
(1 5 4 2 8) (1 4 5 2 8), меняет элементы местами, так как 4>4>(5>4)
(1 4 5 2 8) (1 4 2 5 8), меняет элементы местами, так как 2>(5>2)
(1 4 2 5 8 ) (1 4 2 5 8 ), ввиду того, что элементы стоят на своих местах (5>8>5), алгоритм не меняет их местами.
( 1 4 2 5 8) ( 1 4 2 5 8)
(1 4 2 5 8) (1 2 4 5 8), меняет элементы местами, так как (4>2)2>
(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) )
Сортировка пузырьком в python. Bubble sort in Python
(1 2 4 5 8 ) -> (1 2 4 5 8 )
Теперь массив отсортирован, и алгоритм может быть завершён.
Ниже в качестве примера приведена сортировка пузырьком С :
// C программа реализации пузырьковой сортировки #include void swap(int *xp, int *yp) < int temp = *xp; *xp = *yp; *yp = temp; >// функция реализации пузырьковой сортировки void bubbleSort(int arr[], int n) < int i, j; for (i = 0; i < n-1; i++) // Последние i элементы уже на месте for (j = 0; j < n-i-1; j++) if (arr[j] >arr[j+1]) swap(arr[j+1]); > /* Функция вывода массива на экран */ void printArray(int arr[], int size) < int i; for (i=0; i < size; i++) printf(«%d «, arr[i]); printf(«n»); >// Программа тестирования функций, приведенных выше int main() < int arr[] = ; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); printf(«Sorted array: n»); printArray(arr, n); return 0; >
Сортировка пузырьком Java
// Java программа реализации пузырьковой сортировки class BubbleSort < void bubbleSort(int arr[]) < int n = arr.length; for (int i = 0; i < n-1; i++) for (int j = 0; j < n-i-1; j++) if (arr[j] >arr[j+1]) < // меняем местами temp и arr[i] int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; >> /* Вывод массива на экран */ void printArray(int arr[]) < int n = arr.length; for (int i=0; i// Метод, тестирующий функции, приведенные выше public static void main(String args[]) < BubbleSort ob = new BubbleSort(); int arr[] = ; ob.bubbleSort(arr); System.out.println(«Sorted array»); ob.printArray(arr); > >
Сортировка пузырьком Python
# Python реализация сортировки пузырьком def bubbleSort(arr): n = len(arr) # Проход через все элементы массива for i in range(n): # Последние i элементы уже на месте for j in range(0, n-i-1): # проход массива от 0 до n-i-1 # Поменять местами, если найденный элемент больше # чем следующий элемент if arr[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j] # Код тестирования arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print («Сортированный массив:») for i in range(len(arr)): print («%d» %arr[i]),
Сортированный массив: 11 12 22 25 34 64 90
Как работает сортировка пузырьком
Приведенная выше сортировка методом пузырька всегда выполняется, даже если массив отсортирован. Ее можно оптимизировать путем остановки алгоритма, применяемой в том случае, если внутренний цикл не произвел никакой замены.
// Оптимизированная реализация пузырьковой сортировки #include void swap(int *xp, int *yp) < int temp = *xp; *xp = *yp; *yp = temp; >// Оптимизированная версия пузырьковой сортировки void bubbleSort(int arr[], int n) < int i, j; bool swapped; for (i = 0; i < n-1; i++) < swapped = false; for (j = 0; j < n-i-1; j++) < if (arr[j] >arr[j+1]) < swap(arr[j+1]); swapped = true; >> // Если в процессе прохода не было ни одной замены, то выход из функции if (swapped == false) break; > > /* Функция вывода массива */ void printArray(int arr[], int size) < int i; for (i=0; i < size; i++) printf(«%d «, arr[i]); printf(«n»); >// Программа тестирования функций, приведенных выше int main() < int arr[] = ; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); printf(«Сортированный массив: n»); printArray(arr, n); return 0; >
Пузырьковая сортировка Python 3
# Оптимизированная реализация Python3 # сортировки пузырьком # Оптимизированная версия пузырьковой сортировки def bubbleSort(arr): n = len(arr) # Проход через все элементы массива for i in range(n): swapped = False # Последние i элементы уже # на месте for j in range(0, n-i-1): # проход через массив от 0 # n-i-1. Поменять местами элементы, если # найденный элемент больше # следующего if arr[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True # Если в процессе прохода не было ни одной замены, # то выход из функции if swapped == False: break # тестирующий код arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print («Сортированный массив :») for i in range(len(arr)): print («%d» %arr[i],end=» «)
Метод пузырька C — результат сортировки:
Сортированный массив: 11 12 22 25 34 64 90
Худшая и средняя сложность времени: O (n * n). Наихудший случай возникает, когда массив отсортирован по обратному адресу.
Сложность наилучшего случая: O (n). Наилучший случай возникает, когда массив уже отсортирован.
Пограничные случаи: сортировка занимает минимальное время (порядок n), когда элементы уже отсортированы.
Сортировка на месте: Да.
В компьютерной графике пузырьковая сортировка популярна благодаря возможности обнаруживать мелкие ошибки ( например, обмен всего двух элементов ) в почти отсортированных массивах и исправлять ее только с линейной сложностью ( 2n ). Например, она используется в алгоритме заполнения полигонов, где ограничивающие линии сортируются по их координате x на определенной линии сканирования ( линия, параллельная оси X ), и с увеличением Y их порядок меняется ( два элемента меняются местами ) только на пересечениях двух линий.
Источник: www.internet-technologies.ru
Сортировка методом пузырька
Отсортировать массив, заполненный случайными числами, по возрастанию. Для сортировки использовать метод «пузырька». Вывести на экран массив в исходном и отсортированном виде.
Сортировка методом пузырька заключается в том, что по массиву осуществляются множественные проходы. На каждом проходе очередной элемент сравнивается со следующим за ним. И если он больше (при сортировке по возрастанию), то элементы массива меняются местами.
Таким образом при первом проходе по массиву при сортировке по возрастанию последним в массиве оказывается самое большое значение. При следующем проходе на предпоследнем месте окажется максимальное из оставшихся чисел. Сравнивать последнее и предпоследнее числа нет смысла. Поэтому количество просматриваемых элементов массива на каждом проходе сокращается на 1. Количество проходов равно количеству элементов массива за вычетом единицы, т.к. происходит попарное сравнение.
Pascal
сортировка пузырьком паскаль
const
N = 10;
var
arr: array[1..N] of integer;
i, j, k: integer;
begin
randomize;
for i:=1 to N do begin
arr[i] := random(256);
write (arr[i]:4);
end;
writeln;
for i:=1 to N-1 do
for j:=1 to N-i do
if arr[j] > arr[j+1] then begin
k := arr[j];
arr[j] := arr[j+1];
arr[j+1] := k
end;
for i:=1 to N do
write (arr[i]:4);
writeln;
end.
97 8 156 88 3 99 217 170 135 133
3 8 88 97 99 133 135 156 170 217
Язык Си
#include
#define N 10
main() int a[N], i, j, b;
srand(time(NULL));
for (i=0; i < N; i++) a[i] = rand()%100;
printf(«%3d», a[i]);
>
printf(«n»);
for (i=0; i < N-1; i++) for (j=0; j < N-i-1; j++) if (a[j] > a[j+1]) b = a[j];
a[j] = a[j+1];
a[j+1] = b;
>
>
>
for (i=0; i < N; i++)
printf(«%3d», a[i]);
printf(«n»);
>
71 62 25 3 46 61 25 31 56 12
3 12 25 25 31 46 56 61 62 71
Python
сортировка пузырьком Python (питон)
from random import random
a = [0]*10
for i in range(10):
a[i] = int(random()*100)
print(a)
for i in range(9):
for j in range(9-i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
print(a)
[42, 9, 95, 78, 59, 14, 50, 79, 54, 84]
[9, 14, 42, 50, 54, 59, 78, 79, 84, 95]
В Питоне при обмене значений переменных можно обойтись без буферной переменной. Это делается с помощью присваивания в одном выражении. Такая возможность существует, т.к. в Python перед присваиванием в подобных выражениях сначала формируются кортежи.
КуМир
алг сортировка пузырьком
нач
цел N = 10
цел таб arr[1:N]
цел i,j,k
нц для i от 1 до N
arr[i] := int(rand(0,100))
вывод arr[i], » »
кц
вывод нс
нц для i от 1 до N-1
нц для j от 1 до N-i
если arr[j] > arr[j+1] то
k := arr[j]
arr[j] := arr[j+1]
arr[j+1] := k
все
кц
кц
нц для i от 1 до N
вывод arr[i], » »
кц
кон
41 38 95 61 71 1 20 14 83 61
1 14 20 38 41 61 61 71 83 95
Basic-256
dim a(10)
for i =0 to 9
a[i] = int(rand()*100)
print a[i] + » «;
next i
print
for i=0 to 8
for j=0 to 8-i
if a[j] > a[j+1] then
b = a[j]
a[j] = a[j+1]
a[j+1] = b
endif
next j
next i
for i =0 to 9
print a[i] + » «;
next i
6 61 17 0 51 36 43 32 88 6
0 6 6 17 32 36 43 51 61 88
Источник: gospodaretsva.com
Пузырьковая сортировка в C++: главные моменты
Всем привет! Наверно всем прогерам в какой-то момент нужно было отсортировать массив. Сегодня мы разберем алгоритм сортировки с помощью которого вы сможете отсортировать ваш массив или вектор. Вы наверное догадались с названия сегодня пойдет речь о пузырьковой сортировке.
Этот алгоритм очень просто реализовать, но в то же время его главный минус — медленная сортировка.
Что такое пузырьковая сортировка
Пузырьковая сортировка — наверно самая простая сортировка, которую я встречал. Обычно она встречается в книгах по программированию и не выходит за ее пределы. Так как она работает намного медленнее, чем другие алгоритмы сортировки.
Но благодаря ей появились алгоритмы, которые более эффективнее чем она сама. Из таких сортировок можно отметить шейкерную или как еще ее называют сортировка перемешиванием.
Как работает алгоритм пузырьковой сортировки
Принцип работы пузырьковой сортировки можно описать в три пункта:
- Прохождение по всему массиву;
- Сравнивание между собой пар соседних ячеек;
- Если при сравнении оказывается, что значение ячейки i больше, чем значение ячейки i + 1 , то мы меняем значения этих ячеек местами;
Ниже вы можете увидеть, как работает пузырьковая сортировка в действии.
Как создать пузырьковую сортировку
Вот что нам придется делать для создания пузырьковой сортировки:
- Создать два цикла for , чтобы проходить по всем элементам массива N раз ( N это размер массива).
- Сравнивать ячейки массива, с помощью оператора ветвления if .
- Менять местами значения ячеек.
В примере ниже мы предложили пользователю заполнить массив, который мы дальше отсортируем используя пузырьковую сортировку.
using namespace std ;
setlocale ( LC_ALL , «rus» ) ;
int digitals [ 10 ] ; // объявили массив на 10 ячеек
cout << «Введите 10 чисел для заполнения массива: » << endl ;
for ( int i = 0 ; i < 10 ; i ++ ) <
cin >> digitals [ i ] ; // «читаем» элементы в массив
for ( int i = 0 ; i < 10 ; i ++ ) <
for ( int j = 0 ; j < 9 ; j ++ ) <
if ( digitals [ j ] > digitals [ j + 1 ] ) <
int b = digitals [ j ] ; // создали дополнительную переменную
digitals [ j ] = digitals [ j + 1 ] ; // меняем местами
digitals [ j + 1 ] = b ; // значения элементов
cout << «Массив в отсортированном виде: » ;
for ( int i = 0 ; i < 10 ; i ++ ) <
cout << digitals [ i ] << » » ; // выводим элементы массива
system ( «pause» ) ;
Давайте поподробнее разберем строки 16 — 24 (здесь находится пузырьковая сортировка):
- В строке 16: мы создали первый цикл for .
- В строке 17: аналогично был создан второй, но уже вложенный цикл.
- В строке 18: происходит сравнивание двух элементов.
- Если результат этого условия положительный , то мы меняем значение элементов.
- Если же результат отрицателен , то мы пропускаем этап смены значений.
- В строке 19: создали переменную b , чтобы менять значения ячеек digitals[i] и digitals[i + 1] местами.
Давайте посмотрим, что выведет программа выше при запуске:
sort_puzerek.cpp
Введите 10 чисел для заполнения массива:
5 3 6 2 7 0 2 8 9 10
Массив в отсортированном виде: 0 2 2 3 5 6 7 8 9 10
Process returned 0 (0x0) execution time : 0.005 s
Press any key to continue.
Как улучшить пузырьковую сортировку
Ниже вы можете видеть оптимизированную версию пузырьковой сортировки.
for ( int i = 0 ; i < 10 ; i ++ ) <
bool flag = true ;
for ( int j = 0 ; j < 10 — ( i + 1 ) ; j ++ ) <
if ( digitals [ j ] > digitals [ j + 1 ] ) <
flag = false ;
swap ( digitals [ j ] , digitals [ j + 1 ] ) ;
Давайте посмотрим, что мы сделали для ее оптимизации:
-
В строке 17: изменили условие внутреннего цикла на i < 10 — ( i + 1) .
Дело в том, что за первый полный проход циклом по массиву самый большой элемент всплывет вверх (переместится в конец массива). Второй по размерам элемент всплывет на предпоследнюю ячейку уже за второй проход цикла и т.д.
Поэтому чтобы лишний раз не сравнивать элементы массива тратя на это время, мы решили уменьшать отрезок внутреннего цикла на 1, после каждого полного прохода внешнего цикла.
Для этого в строке 5: чтобы пузырьковая сортировка останавливалась (когда массив уже стал отсортирован), мы объявили булеву переменную flag (ее обычно называют флаг или флажок). Еще при ее инициализации мы поместили значение true , но она меняется на:
- false , если результат условия в строке 4: положительный .
Вы также можете объявить переменную flag типа int и вместо true или false хранить в переменной значение 1 и 0.
А в строке 9: чтобы мы могли выйти из алгоритма мы проверяем:
- Если булева переменная равна true , значит массив уже полностью отсортирован и можно выйти. Для этого используем оператор break .
- Если же значение flag равно false , то продолжаем сортировать массив.
В строке 6: вы (возможно) увидели незнакомую функцию swap . Если коротко описать что она делает, то она принимает два аргумента (через запятую) и меняет их значения местами. В нашем случаи она принимает ячейки digitals[j] и digitals[j + 1] . Мы использовали эту функцию чтобы не писать вот эти 3 строчки:
Источник: codelessons.ru