2.Презентация 08

1. Сортировка, поиск, регулярные выражения

Занятие №8
Сортировка, поиск,
регулярные выражения

2. Что такое сортировка?

3.

1. Что такое сортировка?
Сортировка – это расстановка элементов
массива в заданном порядке.
Варианты сортировки по возрастанию, убыванию,
последней цифре, сумме делителей, по алфавиту.
Алгоритмы:
•простые и понятные, но неэффективные для
больших массивов
▫метод пузырька
•сложные, но эффективные
▫быстрая сортировка (QuickSort)
▫сортировка Шелла (Shell Sort)
▫сортировка слиянием (MergeSort)

4. 1. Функция sorted()

5. 1. Функция sorted

Функция sorted() возвращает
новый
отсортированный
список итерируемого объекта
(списка, словаря, кортежа).
По умолчанию она сортирует
его по возрастанию.

6. Функция sorted

Сортировка строк осуществляется по ASCIIзначениям.
Возвращаемое значение — List (список).
Синтаксис:
sorted(iterable,key=None,reverse=False).
iterable: строка, список, кортеж, множество,
словарь
key (необязательный параметр): если указать
ключ, то сортировка будет выполнена по
функции этого ключа.
reverse (необязательный параметр): по
умолчанию сортировка выполняется по
возрастанию. Если указать reverse=True, то
можно отсортировать по убыванию.

7. 2. Метод list.sort()

8. 2. Метод list.sort()

Метод списков list.sort(), который
изменяет исходный список (и
возвращает None во избежание
путаницы).
Отличие заключается в том, что метод list.sort() определён
только для списков, в то время как sorted() работает со всеми
итерируемыми объектами.

9. Сортировка по возрастанию и сортировка по убыванию в Python

10. reverse

У list.sort() и sorted() есть
параметр reverse, принимающий
boolean-значение.
Он нужен для обозначения
сортировки по убыванию.

11. 3. Сортировка пузырьком это?

12. 3. Сортировка пузырьком это?

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

13. 4. Сортировка вставкой (Insertion sort) это?

14. 4. Сортировка вставкой (Insertion sort) это?

Пример работы "в голове":
Допустим, у нас массив:
[5, 3, 4, 1, 2]
i = 1, key = 3
→ сравниваем с 5 → 5 > 3 → сдвигаем 5
→ вставляем 3 → массив: [3, 5, 4, 1, 2]
i = 2, key = 4
→ сравниваем с 5 → 5 > 4 → сдвигаем 5
→ сравниваем с 3 → 3 < 4 → вставляем → [3, 4,
5, 1, 2]
i = 3, key = 1
→ сдвигаем 5, 4, 3 → вставляем 1 → [1, 3, 4, 5, 2]
i = 4, key = 2
→ сдвигаем 5, 4, 3 → вставляем 2 → [1, 2, 3, 4, 5]

15. 5. Сортировка выбором (Selection sort) это?

16. 5. Сортировка вставкой (Insertion sort) это?

Как работает:
Допустим, у нас массив: [5, 3, 4, 1, 2]
i=0
→ ищем минимум в [5, 3, 4, 1, 2] → это 1
→ меняем 5 и 1 → массив: [1, 3, 4, 5, 2]
i=1
→ ищем минимум в [3, 4, 5, 2] → это 2
→ меняем 3 и 2 → [1, 2, 4, 5, 3]
i=2
→ минимум в [4, 5, 3] → это 3
→ меняем 4 и 3 → [1, 2, 3, 5, 4]
i=3
→ минимум в [5, 4] → это 4
→ меняем 5 и 4 → [1, 2, 3, 4, 5]
i=4
→ последний элемент, уже на месте

17. 6. Сортировка слиянием (mergesort) это?

18. 6. Сортировка слиянием (mergesort) это?

Исходный массив делится на две примерно
равные части. Если массив имеет нечетное
количество элементов, одна из этих «половин» на
один элемент больше, чем другая.
Подмассивы делятся снова и снова на две
половины, пока вы не получите массивы, которые
имеют только один элемент каждый.
Затем вы объединяете пары одноэлементных
массивов в двухэлементные массивы, сохраняя их
в процессе. Затем эти отсортированные пары
объединяются в четырехэлементные массивы и
так далее до тех пор, пока не будет получен
исходный отсортированный массив.

19. 6. Сортировка слиянием (mergesort) это?

20. 7. Быстрая сортировка (QuickSort) это?

21. 7. Быстрая сортировка (QuickSort) это?

Идея: выгоднее
переставлять элементы,
который находятся дальше
друг от друга.
Ч.Э.Хоар 1960
6
5
4
3
2
1
1
5
4
3
2
6
1
2
4
3
5
6
1
2
3
4
5
6
Практический пример

22. 8. Сортировка Шелла (Shell sort) это?

23. 8. Сортировка Шелла (Shell sort) это?

Сортировка Шелла является
оптимизированным вариантом сортировки
вставками.
Оптимизация достигается путем сравнения
не только соседних элементов, но и
элементов на определенном расстоянии,
которое в течении работы алгоритма
уменьшается. На последней итерации это
расстояние равно 1.
После этого алгоритм становится обычным
алгоритмом сортировки вставками, что
гарантирует правильный результат
сортировки.
Но следует отметить один момент: к тому
времени, когда это произойдет, наш
массив будет почти отсортирован, поэтому
итерации будут выполнятся очень быстро.
Практический пример
Результат программы:

24. 8. Сортировка Шелла (Shell sort) это?

Допустим, массив:
[8, 5, 3, 7, 2, 6, 4, 1]
n = 8, значит:
Шаг 1: gap = 4
Сравниваем элементы через 4 позиции:
arr[4] и arr[0], arr[5] и arr[1], ...
Массив начинает частично упорядочиваться по группам
Шаг 2: gap = 2
Сравниваем элементы через 2 позиции
В каждой подгруппе по индексу: [0,2,4,6] и [1,3,5,7] — делаем
сортировку вставками
Шаг 3: gap = 1
Обычная сортировка вставками — но теперь массив почти
отсортирован, поэтому быстро работает