[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:10.50,0:00:13.49,Default,,0000,0000,0000,,Занятие 1 Пузырьковая сортировка
Dialogue: 0,0:00:13.49,0:00:16.92,Default,,0000,0000,0000,,Для этого курса вам понадобятся базовые знания алгебры
Dialogue: 0,0:00:18.50,0:00:21.68,Default,,0000,0000,0000,,Пузырьковая сортировка это простейшая процедура сортировки
Dialogue: 0,0:00:22.29,0:00:24.56,Default,,0000,0000,0000,,В этом контексте сортировка означает упорядочивание масссива
Dialogue: 0,0:00:24.56,0:00:26.55,Default,,0000,0000,0000,,данных в виде целых чисел
Dialogue: 0,0:00:27.78,0:00:31.66,Default,,0000,0000,0000,,Сначала представьте массив с элементами, которые мы хотим сортировать
Dialogue: 0,0:00:32.31,0:00:35.15,Default,,0000,0000,0000,,Мы используем пустой массив для примера
Dialogue: 0,0:00:35.15,0:00:38.08,Default,,0000,0000,0000,,Алгоритм пузырьковой сортировки описывается следующим образом
Dialogue: 0,0:00:39.17,0:00:43.67,Default,,0000,0000,0000,,Мы сравниваем первые два элемента массива и, если они не подряд , мы меняем их позиции
Dialogue: 0,0:00:43.67,0:00:48.100,Default,,0000,0000,0000,,продолжаем делать это для соседних элементов массива до последнего элемента
Dialogue: 0,0:00:48.100,0:00:53.03,Default,,0000,0000,0000,,На этом этапе последний элемент является самым большим в массиве
Dialogue: 0,0:00:53.25,0:00:57.47,Default,,0000,0000,0000,,далее мы повторяем процедуру для всех пар, кроме последнего
Dialogue: 0,0:00:57.47,0:01:00.91,Default,,0000,0000,0000,,до тех пор пока масссив полностью не отсортирован
Dialogue: 0,0:01:07.08,0:01:11.73,Default,,0000,0000,0000,,Теперь заполним массив данными, чтобы показать работу алгоритма
Dialogue: 0,0:01:11.73,0:01:13.80,Default,,0000,0000,0000,,Начнем с сравнения 5 с 9
Dialogue: 0,0:01:13.80,0:01:17.36,Default,,0000,0000,0000,,Поскольку 5 меньше 9, мы ничего не делаем
Dialogue: 0,0:01:17.36,0:01:20.03,Default,,0000,0000,0000,,Затем мы сравниваем 9 с 2
Dialogue: 0,0:01:20.03,0:01:23.58,Default,,0000,0000,0000,,Поскольку 9 больше 2, мы меняем их местами
Dialogue: 0,0:01:23.58,0:01:30.18,Default,,0000,0000,0000,,Делаем то же самое, пока 9, который является самым большим элементом, не достигнет последней позиции
Dialogue: 0,0:01:30.18,0:01:32.70,Default,,0000,0000,0000,,Вот почему алгоритм получил название пузырьковой сортировки
Dialogue: 0,0:01:32.70,0:01:34.85,Default,,0000,0000,0000,,Когда 9 достигает последней позиции
Dialogue: 0,0:01:34.87,0:01:40.63,Default,,0000,0000,0000,,мы продолжаем со следующими шагами алгоритма и сортируем массив
Dialogue: 0,0:01:50.61,0:01:53.83,Default,,0000,0000,0000,,Псевдокод для алгоритма Пузырьковой сортировки довольно прост
Dialogue: 0,0:01:53.83,0:01:57.49,Default,,0000,0000,0000,,Всего эти 4 строки что вы видите
Dialogue: 0,0:01:59.20,0:02:02.19,Default,,0000,0000,0000,,Пузырьковый алгоритм медленный
Dialogue: 0,0:02:02.19,0:02:06.18,Default,,0000,0000,0000,,Чтобы показать вам, что мы имеем в виду, мы рассчитаем его производительность
Dialogue: 0,0:02:06.18,0:02:09.15,Default,,0000,0000,0000,,Предположим, у нас есть массив N элементов
Dialogue: 0,0:02:09.16,0:02:13.06,Default,,0000,0000,0000,,В первом проходе мы выполняем n-1 сравнений
Dialogue: 0,0:02:13.10,0:02:16.08,Default,,0000,0000,0000,,\Nчтобы перейти к самому большому предмету в конце массива
Dialogue: 0,0:02:16.08,0:02:19.30,Default,,0000,0000,0000,,В следующем шаге мы выполним n-2 сравнения
Dialogue: 0,0:02:19.30,0:02:21.71,Default,,0000,0000,0000,,и продолжая таким же образом, мы получаем следующую сумму:
Dialogue: 0,0:02:21.71,0:02:23.62,Default,,0000,0000,0000,,Количество сравнений = (n-1) + (n-2) + ... + 1
Dialogue: 0,0:02:23.62,0:02:36.82,Default,,0000,0000,0000,,по операциям указанная сумма равна n (n-1) / 2, что равно (n ^ 2)/2 - n / 2
Dialogue: 0,0:02:36.82,0:02:42.08,Default,,0000,0000,0000,,При больших значениях n ^ 2 превалирует над другими членами
Dialogue: 0,0:02:42.08,0:02:47.94,Default,,0000,0000,0000,,и мы говорим, что пузырьковый алгоритм имеет сложность порядка n ^ 2