1
00:00:10,500 --> 00:00:13,492
Занятие 1 Пузырьковая сортировка

2
00:00:13,492 --> 00:00:16,915
Для этого курса вам понадобятся базовые знания алгебры

3
00:00:18,500 --> 00:00:21,676
Пузырьковая сортировка это простейшая процедура сортировки

4
00:00:22,288 --> 00:00:24,555
В этом контексте сортировка означает упорядочивание масссива

5
00:00:24,555 --> 00:00:26,546
данных в виде целых чисел

6
00:00:27,776 --> 00:00:31,661
Сначала представьте массив с элементами, которые мы хотим сортировать

7
00:00:32,307 --> 00:00:35,146
Мы используем пустой массив для примера

8
00:00:35,146 --> 00:00:38,076
Алгоритм пузырьковой сортировки описывается следующим образом

9
00:00:39,169 --> 00:00:43,669
Мы сравниваем первые два элемента массива и, если они не подряд , мы меняем их позиции

10
00:00:43,669 --> 00:00:48,996
продолжаем делать это для соседних элементов массива до последнего элемента

11
00:00:48,996 --> 00:00:53,030
На этом этапе последний элемент является самым большим в массиве

12
00:00:53,246 --> 00:00:57,469
далее мы повторяем процедуру для всех пар, кроме последнего

13
00:00:57,469 --> 00:01:00,907
до тех пор пока масссив полностью не отсортирован

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

15
00:01:11,730 --> 00:01:13,800
Начнем с сравнения 5 с 9

16
00:01:13,800 --> 00:01:17,361
Поскольку 5 меньше 9, мы ничего не делаем

17
00:01:17,361 --> 00:01:20,030
Затем мы сравниваем 9 с 2

18
00:01:20,030 --> 00:01:23,576
Поскольку 9 больше 2, мы меняем их местами

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

20
00:01:30,184 --> 00:01:32,698
Вот почему алгоритм получил название пузырьковой сортировки

21
00:01:32,698 --> 00:01:34,853
Когда 9 достигает последней позиции

22
00:01:34,869 --> 00:01:40,626
мы продолжаем со следующими шагами алгоритма и сортируем массив

23
00:01:50,611 --> 00:01:53,834
Псевдокод для алгоритма Пузырьковой сортировки довольно прост

24
00:01:53,834 --> 00:01:57,488
Всего эти 4 строки что вы видите

25
00:01:59,196 --> 00:02:02,188
Пузырьковый алгоритм медленный

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

27
00:02:06,184 --> 00:02:09,146
Предположим, у нас есть массив N элементов

28
00:02:09,161 --> 00:02:13,057
В первом проходе мы выполняем n-1 сравнений

29
00:02:13,100 --> 00:02:16,076

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

30
00:02:16,076 --> 00:02:19,300
В следующем шаге мы выполним n-2 сравнения

31
00:02:19,300 --> 00:02:21,707
и продолжая таким же образом, мы получаем следующую сумму:

32
00:02:21,707 --> 00:02:23,623
Количество сравнений = (n-1) + (n-2) + ... + 1

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

34
00:02:36,815 --> 00:02:42,084
При больших значениях n ^ 2 превалирует над другими членами

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