Algorithms Lesson 1: Bubblesort

Занятие 1 Пузырьковая сортировка

Для этого курса вам понадобятся базовые знания алгебры

Пузырьковая сортировка это простейшая процедура сортировки

В этом контексте сортировка означает упорядочивание масссива

данных в виде целых чисел

Сначала представьте массив с элементами, которые мы хотим сортировать

Мы используем пустой массив для примера

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

Мы сравниваем первые два элемента массива и, если они не подряд , мы меняем их позиции

продолжаем делать это для соседних элементов массива до последнего элемента

На этом этапе последний элемент является самым большим в массиве

далее мы повторяем процедуру для всех пар, кроме последнего

до тех пор пока масссив полностью не отсортирован

Теперь заполним массив данными, чтобы показать работу алгоритма

Начнем с сравнения 5 с 9

Поскольку 5 меньше 9, мы ничего не делаем

Затем мы сравниваем 9 с 2

Поскольку 9 больше 2, мы меняем их местами

Делаем то же самое, пока 9, который является самым большим элементом, не достигнет последней позиции

Вот почему алгоритм получил название пузырьковой сортировки

Когда 9 достигает последней позиции

мы продолжаем со следующими шагами алгоритма и сортируем массив

Псевдокод для алгоритма Пузырьковой сортировки довольно прост

Всего эти 4 строки что вы видите

Пузырьковый алгоритм медленный

Чтобы показать вам, что мы имеем в виду, мы рассчитаем его производительность

Предположим, у нас есть массив N элементов

В первом проходе мы выполняем n-1 сравнений

чтобы перейти к самому большому предмету в конце массива

В следующем шаге мы выполним n-2 сравнения

и продолжая таким же образом, мы получаем следующую сумму:

Количество сравнений = (n-1) + (n-2) + ... + 1

по операциям указанная сумма равна n (n-1) / 2, что равно (n ^ 2)/2 - n / 2

При больших значениях n ^ 2 превалирует над другими членами

и мы говорим, что пузырьковый алгоритм имеет сложность порядка n ^ 2