Сортировка пузырьком

Difference between Selection, Bubble and Insertion Sort

• In terms of algorithm
  • In Bubble sort, adjacent elements are compared and sorted if they are in the wrong order.
  • In Selection Sort, we select the smallest element and swap it with the 0th index element in the first iteration. This selection continues for n-1 elements and the single element is already sorted and we will have array sorted by 1 element in every iteration
  • In Insertion sort, we create partitions of sorted and unsorted parts. One by one element from the sorted art is taken and sent to the unsorted part for checking and placing it to the right position in sorting using swaps.

• In terms of time and space complexity
  • All 3 sort have O(n2) time complexity. But via flag variable we can reduce the time complexity of bubble and insertion to O(n) is the best case.
  • Space Complexity is the same for all i.e., O(1)

	Best	Average	Worst	Space
Selection	O(n2)	O(n2)	O(n2)	O(1)
Bubble	O(n)	O(n2)	O(n2)	O(1)
Insertion	O(n)	O(n2)	O(n2)	O(1)

• In terms of speed
  • Bubble sort is slower than the maximum sort algorithm.
  • There are a lot of swaps that might take place in the worst case.

• In terms of in-place
  • In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space.
  • Selection, Bubble and Insertion are in-place algorithms and do not require any auxiliary memory.

• In terms of stability
  • Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same.
  • Bubble and Insertion are stable algorithms but the naive selection is not as swapping may cost stability.

Selection	Bubble	Insertion
Select smallest in every iteration do single swap	An adjacent swap of every element with the other element where ordering is incorrect	Take and put the element one by one and put it in the right place in the sorted part.
Best case time complexity is O(n2)	Best case time complexity is O(n)	Best case time complexity is O(n)
Works better than bubble as no of swaps are significantly low	Worst efficiency as too many swaps are required in comparison to selection and insertion	Works better than bubble as no of swaps are significantly low
It is in-place	It is in-place	It is in-place
Not stable	Stable	Stable

This brings us to the end of this article where we learned about bubble sort and its implementation in different languages. Also, we learned how to optimize this algorithm to get better performance. I would highly suggest to take up this free course for data structures and algorithms to improve your coding skills.

Алгоритм

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N−1{\displaystyle N-1} раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде. Отсюда и название алгоритма).

Метод пузырька

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

В общем случае алгоритм сортировки пузырьком следующий:

1. Сравнить текущий элемент со следующим.
2. Если следующий элемент меньше/больше текущего, поменять их местами.
3. Если массив отсортирован, закончить алгоритм, иначе перейти на шаг 1.

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

Внешний цикл в худшем случае совершает N (кол-во элементов) — 1 проходов, то есть внутренний цикл выполняется N-1 раз.

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

Если рассмотреть реализацию алгоритма, то можно легко заметить, что время его работы (количество операций) значительно возрастает с увеличением количества элементов сортируемой последовательности.

Скорость сортировки в Python

Python

# speed/main.py

import random

from boxx import timeit

def list_sort(arr):
return arr.sort()

def sorted_builtin(arr):
return sorted(arr)

def main():
arr =

with timeit(name=»sorted(list)»):
sorted_builtin(arr)

with timeit(name=»list.sort()»):
list_sort(arr)

if __name__ == «__main__»:
main()

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

# speed/main.py   importrandom fromboxx importtimeit deflist_sort(arr) returnarr.sort() defsorted_builtin(arr) returnsorted(arr) defmain() arr=random.randint(,50)forrinrange(1_000_000) withtimeit(name=»sorted(list)») sorted_builtin(arr) withtimeit(name=»list.sort()») list_sort(arr) if__name__==»__main__» main()

Указанный выше код выводит следующий результат:

Shell

$ python main.py
«sorted(list)» spend time: 0.1104379
«list.sort()» spend time: 0.0956471

1 2 3

$python main.py «sorted(list)»spend time0.1104379 «list.sort()»spend time0.0956471

Как видите, метод немного быстрее, чем функция . Почему так получается? Разберем обе функции и посмотрим, сможет ли байтовый код дать ответ:

Python

>>> import dis
>>> dis.dis(list_sort)
12 0 LOAD_FAST 0 (arr)
2 LOAD_METHOD 0 (sort)
4 CALL_METHOD 0
6 RETURN_VALUE
>>> dis.dis(sorted_builtin)
16 0 LOAD_GLOBAL 0 (sorted)
2 LOAD_FAST 0 (arr)
4 CALL_FUNCTION 1
6 RETURN_VALUE

1 2 3 4 5 6 7 8 9 10 11

>>>importdis >>>dis.dis(list_sort) 12LOAD_FAST(arr) 2LOAD_METHOD(sort) 4CALL_METHOD 6RETURN_VALUE >>>dis.dis(sorted_builtin) 16LOAD_GLOBAL(sorted) 2LOAD_FAST(arr) 4CALL_FUNCTION1 6RETURN_VALUE

Байтовый код обеих функций практически идентичен. Единственное различие в том, что функция сначала загружает список, и за методом (sort) следует вызванный метод списка без аргументов. Если сравнить, функция сначала загружает встроенную функцию , а за ней следует список и вызов загруженной функции со списком в качестве аргумента.

Почему же временные результаты отличаются?

Можно предположить, что в то время как может работать с известным размером и менять элементы внутри данного размера, должен работать c неизвестным размером. Следовательно, если при добавлении нового элемента не хватает памяти, нужно изменить размер нового списка, созданного через . На это требуется время! Если просмотреть исходный код CPython, можно найти следующий комментарий об изменении размера списка объектов:

Помните, что сейчас мы работаем со списком из 1 000 000 элементов — изменений размера будет довольно много! К несчастью, пока что это лучший ответ на вопрос, почему на 13% быстрее, чем .

Python

new_array = arr.copy()
arr.sort()

1 2	new_array=arr.copy() arr.sort()

Имплементация приводит к разнице во времени выполнения, поскольку создание копии списка занимает некоторое время.

Description

We can imagine that sorted numbers are bubbles, the ones with lower value are lighter than the ones with higher value, hence they ascend to the surface faster.

Bubble sort advances similarly. In every step it compares two adjacent elements and if the lower value is on the left side of the higher, bubble sort swaps them (lighter value ascends to the end of the array) and with the same logic algorithm proceeds to the next item.

After one iteration the lowest value is located at the end of the array. Algorithm now repeats the procedure with reduced array (the last element is already sorted). After iterations is the array completely sorted, because the last bubble is sorted trivially.

Методы списков

Давайте теперь
предположим, что у нас имеется список из чисел:

a = 1, -54, 3, 23, 43, -45, 

и мы хотим в
конец этого списка добавить значение. Это можно сделать с помощью метода:

a.append(100)

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

a = a.append(100)

категорически не
следует, так мы только потеряем весь наш список! И этим методы списков
отличаются от методов строк, когда мы записывали:

string="Hello"
string = string.upper()

Здесь метод upper возвращает
измененную строку, поэтому все работает как и ожидается. А метод append ничего не
возвращает, и присваивать значение None переменной a не имеет
смысла, тем более, что все работает и так:

a = 1, -54, 3, 23, 43, -45, 
a.append(100)

Причем, мы в методе
append можем записать
не только число, но и другой тип данных, например, строку:

a.append("hello")

тогда в конец
списка будет добавлен этот элемент. Или, булевое  значение:

a.append(True)

Или еще один
список:

a.append(1,2,3)

И так далее. Главное,
чтобы было указано одно конкретное значение. Вот так работать не будет:

a.append(1,2)

Если нам нужно
вставить элемент в произвольную позицию, то используется метод

a.insert(3, -1000)

Здесь мы
указываем индекс вставляемого элемента и далее значение самого элемента.

Следующий метод remove удаляет элемент
по значению:

a.remove(True)
a.remove('hello')

Он находит
первый подходящий элемент и удаляет его, остальные не трогает. Если же
указывается несуществующий элемент:

a.remove('hello2')

то возникает
ошибка. Еще один метод для удаления

a.pop()

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

end = a.pop()

Также в этом
методе можно указывать индекс удаляемого элемента, например:

a.pop(3)

Если нам нужно
очистить весь список – удалить все элементы, то можно воспользоваться методом:

a.clear()

Получим пустой
список. Следующий метод

a = 1, -54, 3, 23, 43, -45, 
c = a.copy()

возвращает копию
списка. Это эквивалентно конструкции:

c = list(a)

В этом можно
убедиться так:

c1 = 1

и список c будет отличаться
от списка a.

Следующий метод count позволяет найти
число элементов с указанным значением:

c.count(1)
c.count(-45)

Если же нам
нужен индекс определенного значения, то для этого используется метод index:

c.index(-45)
c.index(1)

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

c.index(1, 1)

Здесь поиск
будет начинаться с индекса 1, то есть, со второго элемента. Или, так:

c.index(23, 1, 5)

Ищем число 23 с
1-го индекса и по 5-й не включая его. Если элемент не находится

c.index(23, 1, 3)

то метод
приводит к ошибке. Чтобы этого избежать в своих программах, можно вначале
проверить: существует ли такой элемент в нашем срезе:

23 in c1:3

и при значении True далее уже
определять индекс этого элемента.

Следующий метод

c.reverse()

меняет порядок
следования элементов на обратный.

Последний метод,
который мы рассмотрим, это

c.sort()

выполняет
сортировку элементов списка по возрастанию. Для сортировки по убыванию, следует
этот метод записать так:

c.sort(reverse=True)

Причем, этот
метод работает и со строками:

lst = "Москва", "Санкт-Петербург", "Тверь", "Казань"
lst.sort()

Здесь
используется лексикографическое сравнение, о котором мы говорили, когда
рассматривали строки.

Это все основные
методы списков и чтобы вам было проще ориентироваться, приведу следующую
таблицу:

Метод	Описание
append()	Добавляет элемент в конец списка
insert()	Вставляет элемент в указанное место списка
remove()	Удаляет элемент по значению
pop()	Удаляет последний элемент, либо элемент с указанным индексом
clear()	Очищает список (удаляет все элементы)
copy()	Возвращает копию списка
count()	Возвращает число элементов с указанным значением
index()	Возвращает индекс первого найденного элемента
reverse()	Меняет порядок следования элементов на обратный
sort()	Сортирует элементы списка

Как улучшить пузырьковую сортировку

Ниже вы можете видеть оптимизированную версию пузырьковой сортировки.

for (int i = 0; i < 10; i++) {
bool flag = true;
for (int j = 0; j < 10 — (i + 1); j++) {
if (digitals > digitals) {
flag = false;
swap (digitals, digitals);
}
}
if (flag) {
break;
}
}

1 2 3 4 5 6 7 8 9 10 11 12

for(inti=;i<10;i++){ boolflag=true; for(intj=;j<10-(i+1);j++){ if(digitalsj>digitalsj+1){ flag=false; swap(digitalsj,digitalsj+1); } } if(flag){ break; } }

Давайте посмотрим, что мы сделали для ее оптимизации:

1. В строке 17: изменили условие внутреннего цикла на .Поэтому чтобы лишний раз не сравнивать элементы массива тратя на это время, мы решили уменьшать отрезок внутреннего цикла на 1, после каждого полного прохода внешнего цикла.
2. Вы могли заметить, что если даже массив стал отсортирован (или сразу был отсортирован) алгоритм все равно продолжает сравнивать элементы.

Для этого в строке 5: чтобы пузырьковая сортировка останавливалась (когда массив уже стал отсортирован), мы объявили булеву переменную (ее обычно называют флаг или флажок). Еще при ее инициализации мы поместили значение , но она меняется на:

false, если результат условия в строке 4: положительный.

А в строке 9: чтобы мы могли выйти из алгоритма мы проверяем:

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

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

int b = digitals;
digitals = digitals;
digitals = b;

1 2 3

intb=digitalsj; digitalsj=digitalsj+1; digitalsj+1=b;

Использовать ее необязательно, потому что она не сделает код быстрее. Но как мы сказали выше, кода станет меньше.

Как работает Быстрая сортировка

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

Подумайте об этом на мгновение — как бы вы выбрали адекватную опору для вашего массива? В истории быстрой сортировки было представлено много идей о том, как выбрать центральную точку — случайный выбор элемента, который не работает из-за того, что «дорогой» выбор случайного элемента не гарантирует хорошего выбора центральной точки; выбор элемента из середины; выбор медианы первого, среднего и последнего элемента; и еще более сложные рекурсивные формулы.

Самый простой подход — просто выбрать первый (или последний) элемент. По иронии судьбы, это приводит к быстрой сортировке на уже отсортированных (или почти отсортированных) массивах.

Именно так большинство людей выбирают реализацию быстрой сортировки, и, так как это просто и этот способ выбора опоры является очень эффективной операцией, и это именно то, что мы будем делать.

Теперь, когда мы выбрали опорный элемент — что нам с ним делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу опору, указатель на «меньшие» элементы и указатель на «более крупные» элементы.

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

Рассмотрим пошагово то, что мы планируем сделать, это поможет проиллюстрировать весь процесс. Пусть у нас будет следующий список.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)

Выберем первый элемент как опору 29), а указатель на меньшие элементы (называемый «low») будет следующим элементом, указатель на более крупные элементы (называемый «high») станем последний элемент в списке.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

Мы двигаемся в сторону high то есть влево, пока не найдем значение, которое ниже нашего опорного элемента.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

• Теперь, когда наш элемент high указывает на элемент 21, то есть на значение меньше чем опорное значение, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет смысла менять местами значение, которое меньше, чем опорное значение, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который будет больше.
• Мы перемещаем переменную low вправо, пока не найдем элемент больше, чем опорное значение. К счастью, low уже имеет значение 89.
• Мы меняем местами low и high:

29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44

• Сразу после этого мы перемещает high влево и low вправо (поскольку 21 и 89 теперь на своих местах)
• Опять же, мы двигаемся high влево, пока не достигнем значения, меньшего, чем опорное значение, и мы сразу находим — 12
• Теперь мы ищем значение больше, чем опорное значение, двигая low вправо, и находим такое значение 41

Этот процесс продолжается до тех пор, пока указатели low и high наконец не встретятся в одном элементе:

29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,41,99,44

Мы больше не используем это опорное значение, поэтому остается только поменять опорную точку и high, и мы закончили с этим рекурсивным шагом:

28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44

Как видите, мы достигли того, что все значения, меньшие 29, теперь слева от 29, а все значения больше 29 справа.

Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 44,78,87,66,31,76,58,88,83,97,41,99,44 (правая сторона). И так далее.

Сортировка Шелла (Shell Sort)

Алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами.

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

• отсутствие потребности в памяти под стек;
• отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

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

Подробный разбор пузырьковой сортировки

Давайте разберем подробно как работает пузырьковая сортировка

Первая итереация (первый повтор алгоритма) меняет между собой 4 и 2 так как цифра два меньше чем четыре 2<4, повторюсь что алгоритм меняет значения между собой если, слева оно меньше чем справа. Далее происходит сверка между 4 и 3, и так как 3 меньше чем 4 (3<4) происходит обмен значениями. Потом проходит проверку между 4 и 8 и так как значение 4 меньше чем 8 то не происходит обмена, ведь уже и так всё на своих местах.

Далее сравнивается 8 и 1 и так как 1 меньше чем 8 (1<8) и оно не находиться слева то происходит обмен значениями.После это первый повтор алгоритма заканчивается, на анимации я выделил это зеленым фоном.

В итоге по окончанию работы алгоритма пузырьковой сортировки мы имеем следующий порядок числового массива: 2 3 4 1 8

и начинается второй повтор алгоритма.

Далее сравнивается 2 и 3 и так как два меньше чем три и оно находиться слева то просто идем дальше ничего не трогая. Также проверяем и 3 и 4 и тоже самое условие выполняется 3<4 и оно слева. Дальше проверяется 4 и 1 и тут мы видим что число 1<4 и не находиться слева, поэтому алгоритм меняет их местами. В крайний раз для второго повторения алгоритма проверяется 4 и 8, но тут всё в порядке, и мы дошли до конца начинаем третье повторение. Итоги для второго повторения такие : 2 3 1 4 8

Третье повторение пузырькового алгоритма начинается с сравнения 2 и 3, тут алгоритм проверяет что 2<3 и 2 находиться слева и оставляет их в покое и идет дальше. Сравнение же 3 и 1 показывает что 1 то меньше чем три, но почему то не слева и меняет их местами. Далее идет сравнение 3 и 4, тут всё в порядке и так далее до сравнения 4 и 8.

После этого получается следующий результат: 2 1 3 4 8

Как мы видим почти все цифры уже на своих местах и в порядке возрастания! Осталось только в последнем повторении пузырькового алгоритма поменять местами 2 и 1 и всё. После того как алгоритм закончил свою работу и проверил что цифры больше нельзя поменять местами он перестает работать с таким вот результатом: 1 2 3 4 8

Алгоритм

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N−1{\displaystyle N-1} раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде. Отсюда и название алгоритма).

Модификации[править]

Сортировка чет-нечетправить

Сортировка чет-нечет (англ. odd-even sort) — модификация пузырьковой сортировки, основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность — .
Псевдокод указан ниже:

function oddEvenSort(a):
  for i = 0 to n - 1 
    if i mod 2 == 0
      for j = 2 to n - 1 step 2
        if a < a
          swap(a, a)  
    else      
      for j = 1 to n - 1 step 2
        if a < a
          swap(a, a)

Преимущество этой сортировки — на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.

Сортировка расческойправить

Сортировка расческой (англ. comb sort) — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность — , но стремится к . Является самой быстрой квадратичной сортировкой. Недостаток — она неустойчива. Псевдокод указан ниже:

function combSort(a):
  k = 1.3
  jump = n
  bool swapped = true
  while jump > 1 and swapped
    if jump > 1
      jump /= k
    swapped = false
    for i = 0 to size - jump - 1
      if a < a
        swap(a, a)
        swapped = true

Пояснения: Изначально расстояние между сравниваемыми элементами равно , где — оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.

Сортировка перемешиваниемправить

Сортировка перемешиванием (англ. cocktail sort), также известная как Шейкерная сортировка — разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность — , но стремится она к , где — максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:

function shakerSort(a):
  begin = -1
  end = n - 2
  while swapped
    swapped = false   
    begin++
    for i = begin to end 
      if a > a 
        swap(a, a)
        swapped = true    
    if !swapped
      break    
    swapped = false 
    end--
    for i = end downto begin
      if a > a 
        swap(a, a)
        swapped = true

Сортировка пузырьком 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 > arr)

{

// меняем местами temp и arr

int temp = arr;

arr = arr;

arr = temp;

}

}

/* Вывод массива на экран */

void printArray(int arr[])

{

int n = arr.length;

for (int i=0; i<n; ++i)

System.out.print(arr + " ");

System.out.println();

}

// Метод, тестирующий функции, приведенные выше

public static void main(String args[])

{

BubbleSort ob = new BubbleSort();

int arr[] = {64, 34, 25, 12, 22, 11, 90};

ob.bubbleSort(arr);

System.out.println("Sorted array");

ob.printArray(arr);

}

}

Алгоритм

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N−1{\displaystyle N-1} раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде. Отсюда и название алгоритма).

Working of Bubble Sort

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)

1. Starting from the first index, compare the first and the second elements.
2. If the first element is greater than the second element, they are swapped.
3. Now, compare the second and the third elements. Swap them if they are not in order.
4. The above process goes on until the last element.
   Compare the Adjacent Elements

2. Remaining Iteration

The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is placed at the end.

Put the largest element at the end

In each iteration, the comparison takes place up to the last unsorted element.

Compare the adjacent elements

The array is sorted when all the unsorted elements are placed at their correct positions.

The array is sorted if all elements are kept in the right order