Занятие 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