Программирование на Python. Zhuldyz Sotsial - MSc in Mechanical Engineering, NU’21

1.

Программирование на Python
Zhuldyz Sotsial - MSc in Mechanical Engineering, NU’21

2.

Неделя 5.
Урок 21.
2

3.

Содержание урока
Алгоритмы сортировки
Сортировка выбором
Сортировка вставками
Пузырьковая сортировка
3

4.

Алгоритмы сортировки
Алгоритм сортировки используется для переупорядочивания заданного
массива или элементов списка в соответствии с оператором сравнения
элементов. Оператор сравнения используется для определения нового
порядка элементов в соответствующей структуре данных.
В этом уроке мы рассмотрим легкие алгоритмы сортировки
4

5.

Сортировка выбором
Сортировка выбором это алгоритм который находит наименьший элемент и
добавляет его в начало списка. Чтобы это осуществит сортировка выбором
начинает с первого элемента и поочередно сравнивает весь список, чтобы
найти самое минимальное значение. Представим что у нас есть список
элементов показанный ниже.
5

6.

Сортировка выбором
6

7.

Сортировка выбором
7

8.

Сортировка выбором
Список отсортирован!
8

9.

Сортировка вставками
Сортировка вставками добавляет элементы в сортированный список из
несортированного списка. Для этого алгоритм использует нахождения
правильной позиции в отсортированном списке. Представим что у нас есть
список элементов показанный ниже.
9

10.

Сортировка вставками
10

11.

Сортировка вставками
11

12.

Пузырьковая сортировка
Пузырьковая сортировка это алгоритм, который сравнивающий два элемента
по очереди и в соответствии меняет их местами.
12

13.

Пузырьковая сортировка
50 больше чем 30, поэтому элементы меняются местами. Так же и с 40.
13

14.

Пузырьковая сортировка
14

15.

Операция swap
15

16.

Функция пузырьковой сортировки
16

17.

Сортировка выбором без swap и с
В первом случае мы сортируем в отдельный список а во второй функции элементы
сортируются внутри начального списка
17

18.

Сортировка вставками
В первом случае мы сортируем в отдельный список а во второй функции элементы
сортируются внутри начального списка
18

19.

Маленькое задание для самостоятельной работы
Создайте лист от 1 до 999999 элементов.
Используйте функцию shuffle из библиотеки random и перемешайте порядок.
Засеките время работы трёх алгоритмов и скажите который работает
быстрее.
19

20.

Контрольные вопросы
Сколько раз элементы менялись местами внутри списка?
20

21.

Контрольный вопросы
Сколько в общем сравнений было в данной программе?
21

22.

Задача для самостоятельной работы
Напишите программу, которая будет проверять два слова и выяснит
анаграмма это или нет. Анаграмма это слово которое строится из тех же букв
что и предыдущее.
22