WEBVTT

00:00:10.500 --> 00:00:13.492
Занятие 1 Пузырьковая сортировка

00:00:13.492 --> 00:00:16.915
Для этого курса вам понадобятся базовые знания алгебры

00:00:18.500 --> 00:00:21.676
Пузырьковая сортировка это простейшая процедура сортировки

00:00:22.288 --> 00:00:24.555
В этом контексте сортировка означает упорядочивание масссива

00:00:24.555 --> 00:00:26.546
данных в виде целых чисел

00:00:27.776 --> 00:00:31.661
Сначала представьте массив с элементами, которые мы хотим сортировать

00:00:32.307 --> 00:00:35.146
Мы используем пустой массив для примера

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

00:00:39.169 --> 00:00:43.669
Мы сравниваем первые два элемента массива и, если они не подряд , мы меняем их позиции

00:00:43.669 --> 00:00:48.996
продолжаем делать это для соседних элементов массива до последнего элемента

00:00:48.996 --> 00:00:53.030
На этом этапе последний элемент является самым большим в массиве

00:00:53.246 --> 00:00:57.469
далее мы повторяем процедуру для всех пар, кроме последнего

00:00:57.469 --> 00:01:00.907
до тех пор пока масссив полностью не отсортирован

00:01:07.076 --> 00:01:11.730
Теперь заполним массив данными, чтобы показать работу алгоритма

00:01:11.730 --> 00:01:13.800
Начнем с сравнения 5 с 9

00:01:13.800 --> 00:01:17.361
Поскольку 5 меньше 9, мы ничего не делаем

00:01:17.361 --> 00:01:20.030
Затем мы сравниваем 9 с 2

00:01:20.030 --> 00:01:23.576
Поскольку 9 больше 2, мы меняем их местами

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

00:01:30.184 --> 00:01:32.698
Вот почему алгоритм получил название пузырьковой сортировки

00:01:32.698 --> 00:01:34.853
Когда 9 достигает последней позиции

00:01:34.869 --> 00:01:40.626
мы продолжаем со следующими шагами алгоритма и сортируем массив

00:01:50.611 --> 00:01:53.834
Псевдокод для алгоритма Пузырьковой сортировки довольно прост

00:01:53.834 --> 00:01:57.488
Всего эти 4 строки что вы видите

00:01:59.196 --> 00:02:02.188
Пузырьковый алгоритм медленный

00:02:02.188 --> 00:02:06.180
Чтобы показать вам, что мы имеем в виду, мы рассчитаем его производительность

00:02:06.184 --> 00:02:09.146
Предположим, у нас есть массив N элементов

00:02:09.161 --> 00:02:13.057
В первом проходе мы выполняем n-1 сравнений

00:02:13.100 --> 00:02:16.076

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

00:02:16.076 --> 00:02:19.300
В следующем шаге мы выполним n-2 сравнения

00:02:19.300 --> 00:02:21.707
и продолжая таким же образом, мы получаем следующую сумму:

00:02:21.707 --> 00:02:23.623
Количество сравнений = (n-1) + (n-2) + ... + 1

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

00:02:36.815 --> 00:02:42.084
При больших значениях n ^ 2 превалирует над другими членами

00:02:42.084 --> 00:02:47.938
и мы говорим, что пузырьковый алгоритм имеет сложность порядка n ^ 2