Bubble Sort

Введение

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

Алгоритм

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

Производительность

Сортировка пузырьком крайне медленная, сложность - О(n^2), из-за двух вложенных циклов.

Мы можем улучшить ее. так как если у нас, например, массив почти отсортирован, то нам нет смысла ждать все n итераций. Для этого можно завести счетчик swap-ов(или обычный boolean флаг), т.е счетчик перестановок - который будет сигнализировать о том, были ли во время итерации "всплытия", если нет, то массив уже отсортирован, а значит можно выходить из цикла.

Пример кода

//todo example in java code