Лекция+2+Сортировка+1 (1)

1. Сортировка. Квадратичные сортировки (пузырьком, выбором, вставками). Сортировка слиянием.

https://forkettle.ru/vidioteka/programmirovanie-i-set/algoritmy-i-struktury-dannykh/108-sortirovka-i-poiskdlya-chajnikov
https://habr.com/ru/post/414
https://habr.com/ru/post/414653/653/
https://geekbrains.ru/courses/1117

2.

• Краткая аннотация к лекции: Данная лекция
рассматривает
основные
методы
сортировки,
используемые при обработке больших объемов данных.
В
частности,
рассматривается
квадратичные
сортировки, такие как пузырьковая, сортировка
выбором и сортировка вставками, а также более
эффективный метод - сортировка слиянием. Для
каждого метода приведены примеры реализации, его
особенности и оценка времени выполнения.
• Цель лекции: Ознакомить слушателей с методами
сортировки и их применением в различных
задачах.Помочь слушателям понять различия между
квадратичными
сортировками
и
сортировкой
слиянием.Обучить слушателей техникам выбора
подходящего метода сортировки для конкретных задач.

3.

Сортировка
Поиск
Алгоритмы
Оптимизации в
нейронных сетях
Обходы графов

4. Сортировка

Процесс упорядочения множества подобных информационных объектов
в некотором определённом порядке с целью облегчения
последующего поиска нужных элементов.
От типа сортируемого объекта
Сортировка массива
Сортировка файлов
Зачем сортировать массив?
Отсортированный массив способствует быстрому поиску элемента
Среднее количество
элементов, которое надо
перебрать, чтобы найти
элемент с заданным
значением ключа

5.

Сортировка массива
Сортировка файлов
• Внутренняя сортировка, или
сортировка массивов,
оперирует массивами, целиком
помещающимися в
оперативной памяти с
произвольным доступом к
любой ячейке.
• Данные обычно
упорядочиваются на том же
месте без дополнительных
затрат памяти.
• Внешняя сортировка, или
сортировка файлов, оперирует
запоминающими устройствами
большого объёма.
• Доступ к носителю
осуществляется
последовательным образом: в
каждый момент времени можно
считать или записать только
элемент, следующий за
текущим.
• Объём данных не позволяет им
разместиться в ОЗУ.
• Это приводит к специальным
методам упорядочения, обычно
использующим дополнительное
дисковое пространство.

6.

Сортировка массивов
Код
ТОВАР
Наименование
Цена
class Tfruts:
Код
Наименование
Цена
44
Яблоки
35.50
55
Апельсины
29.90
12
Бананы
22.00
...
...
...
Ключ
pass
b = Tfruits()
b.code = “44”
Уникальный
Неуникальный
b.name = “Яблоки”
b.count = “35.50”
…
Сортировка - упорядочение массива в
соответствии со значениями ключа

7.

Алгоритмы сортировки массивов
Внешняя
сортировка
Сортировка
Сортировка с
помощью
включения
Сортировка с
помощью
выделения
n2
Прямое
включение
(вставки)
Двоичное
включение
(вставки)
Выбором
(нахождения
k-й
порядковой
статистики)
Сортировка с
помощью обмена
Прямые
Пузырьковая
n*log(n)
Включение с
уменьшающимися
расстояниями (Шелла)
Шейкерная
Улучшенные
С помощью дерева
Слиянием
Разделение
(быстрая)

8. Как выбрать алгоритм?

- Скорость выполнения алгоритма
- Начальное состояние обрабатываемого
массива
- Сложность реализации
- Требуемый объем памяти
Задачи сортировки
Требуется упорядочить ключи по
возрастанию или по убыванию
Допустим, дана последовательность из
n ключей
а1, а2, … аn
Нужно сделать перестановку (i1, i2, …
in)
по возрастанию
аi1 ≤ аi2, ≤ … ≤ аin
по убыванию
аi1 ≥ аi2 ≥ … ≥ аin
Почему не один
алгоритм
Скорость выполнения
сортировки всех алгоритмов
зависит от начального
состояния сортируемого
массива
Элементы могут располагаться:
- Случайным образом
- Упорядочены или близки к
требуемому положению
- Упорядочены или близки к
требуемому положению в
обратном порядке

9.

Сортировка устойчивая / неустойчивая
При Устойчивой сортировке не меняется относительный
порядок сортируемых элементов, имеющих одинаковые
ключи, а при Неустойчивой сортировке порядок может
измениться

10.

Базовые операции сортировки
1. Сравнение двух
элементов (С = Compare)
А
≥
В
2. Перестановка двух
элементов (M =Move)
А
В
Отличие
различных алгоритмов сортировки состоит
только
в способах выбора пар элементов

11.

Квадратичные сортировки:
- пузырьком
- шейкерная
- выбором
- вставками

12.

Сортировка пузырьком или метод простого
обмена (Bubble-sort)
Алгоритм состоит в повторяющихся проходах по сортируемому
массиву. На каждой итерации последовательно сравниваются
соседние элементы, и, если порядок в паре неверный, то элементы
меняют местами. Необходимо совершить не более n-1 проходов,
где n размер массива, чтобы отсортировать массив. Или как иначе
говорят самые «легкие» элементы массива «всплывают», а самые
«тяжелые» - «тонут».
•Разновидности:
• Метод простого обмена (Пузырёк)
• Пузырёк с флажком
• Метод «Плавающего пузырька»
• Шейкерная сортировка

13.

Сортировка пузырьком или метод простого обмена (Bubble-sort)
Эффективность (n2-n)/2

14.

Сортировка пузырьком или метод простого обмена (Bubble-sort) на Python
A = [7,9,8,1,5,10,12,80]
n = len(A)
for i in range (0, n-1):
for j in range (0, n-1):
if A [j+1] < A [j]:
A[j], A[j+1] = A[j+1], A[j]
print (A)
Наихудший случай:
упорядоченный в обратном
порядке массив
Количество сравнений:
T(N) = (N - 1) + (N - 2) + ... + 1
= (N * (N-1))/2 = O(N2)
Общее время: T(N) = О(N2)
А
n = len(A)
i, (0, n-1)
j, (0,n-1):
нет
A [j+1] <
A [j]
да
A[j], A[j+1] = A[j+1], A[j]
A

15.

Сортировка пузырьком или метод простого обмена (Bubble-sort) на Python

16.

Пузырек с
флажком
• При реализации сортировки данным методом, вводится
вспомогательная переменная «флажок» , для того чтобы не
приходить n-1 раз. Вспомогательная переменная «флажок» перед
проведением очередного прохода позволяет проверять, была ли
произведена перестановка на предыдущем проходе. Если
перестановки не было, значит массив упорядочен и сортировку
можно прекратить.
Плавающий
пузырек
• Если на некотором шаге выполняется просмотр i-го элемента и слева от
него имеется уже упорядоченная последовательность элементов, то в
конечном счете i-й элемент займет любую позицию от 1-й до i-й.
Выполняется движение к концу массива, до тех пор, пока не обнаружится
нарушение сортирующего условия. После соответствующего обмена
элементов начинается движение в обратном направлении до тех пор, пока
выполняются необходимые обмены элементов. Если обменов при
обратном движении уже нет, то движение продолжается с места
остановки. Описанная процедура повторяется до тех пор, пока не будет
достигнут конец массива.
Шейкерная
сортировка
• “Легкие пузырьки” всплывают за один проход, а “тяжелые” – тонут за
несколько проходов. Такая асимметрия вызвала появление новой идеи
сортировки, “пузырьком”, а именно: сортировать не в одну сторону, а
поочередно в обе, т.е. на каждом шаге осуществляется проход как в одну
сторону, так и в другую. Таким образом, на каждом шаге “легкий пузырек”
всплывает на поверхность, а “тяжелый” – тонет.

17.

Шейкерная сортировка (ShakerSort)
- выделенные элементы сравниваются между собой
Эффективность (n2-n(k+ln(n)))/2

18. Шейкерная сортировка

•Шейкерная сортировка
А
left =0
right = len(A)-1
left< =right
-
j, (right, left, -1:
+
i, left, rigth,+1
-
-
+
+
A[i - 1] > A[i]:
A [i] > A [i+1]
A[i], A[i - 1] = A[i - 1], A[i]
A[i], A[i+1] = A[i+1], A[j]
right = right +1
left= left+1
A

19. Шейкерная сортировка

A = [22, 13, 5, 7, 2, 74]
left = 0
right = len(A) - 1
while left <= right:
for i in range(left, right, +1):
print(A)
if A[i] > A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]
right -= 1
for i in range(right, left, -1):
if A[i - 1] > A[i]:
A[i], A[i - 1] = A[i - 1], A[i]
left += 1
print(A)

20. Сортировка выбором (Selection-sort)

Порядок шагов для сортировки:
1. Выбрать минимальный элемент из всего исходного
массива и поместить его на первое место, а первый
элемент – на место минимального
2. Просматривая массив от второго элемента до конца, найти
минимальный элемент и поместить его на второе место, а
второй на место минимального.
3. Повторять эту операцию для каждого элемента

21. Сортировка выбором

Эффективность (n2-n)/2

22. Сортировка выбором

А
j<N
n = len(A)
i= 0
+
-
+
-
+
i<N-1
A[j] < A[m]
m=i
m=j
j=i+1
j=i+1
A[i], A[m] = A[m], A[i]
A
i += 1

23. Сортировка выбором на Python

A = [7, 9, 8, 1, 5, 10, 12, 80]
N = len(A)
i=0
while i < N - 1:
min = i # Переменная min будет хранить индекс ячейки с
минимальным значением.
j = i + 1 # Поиск начинаем с ячейки следующей за i.
while j < N:
if A [j] < A [min]:
min = j
j += 1 # перейдем к следующей ячейке.
A[i], A[min] = A[min], A[i]
i += 1 # переход к следующей необработанной ячейке
print(A)

24. Сортировка слиянием (Merge Sort)

Алгоритм сортировкаи слиянием
1. Исходный массив делится поровну до тех пор, пока количество
элементов подмассива не будет составлять не более двух элементов
2. Сначала в самом массивах элементы сортируются, затем
отсортированные массивы сливаем при котором в один проход цикла
выбираются по одному элементу с каждого массива и сравниваются
между собой.
3. Наименьший элемент отправляется в результирующий (одновременно
во всех подмассивах) происходит сравнение и обмен местами
4. Затем подмассивы объединяются в более крупный и выполняется пункт
2
Сортировка слиянием - классический пример рекурсивного алгоритма: он
использует самого себя для сортировки частей массива.

25.

26.

27. Сортировка слиянием

def merge_sort(nums):
if len(nums) > 1:
mid = len(nums)//2
left = nums[:mid]
right = nums[mid:]
merge_sort (left)
merge_sort (right)
i=j=k=0
while i < len(left) and j
< len(right):
if left[i] < right[j]:
nums[k] = left[i]
i+=1
else:
nums[k] = right[j]
j+=1
k+=1
while i < len(left):
nums[k] = left[i]
i+=1
k+=1
while j < len(right):
nums[k] = right[j]
j+=1
k+=1
nums = [5, 2, 3, 6, 84, 9, 8]
merge_sort(nums)
print(nums)

28. Сортировка включением (вставками)

Сортировка вставками — алгоритм сортировки, в
котором элементы исходной последовательности
просматриваются по одному, и каждый новый
поступивший элемент размещается в подходящее
место среди ранее упорядоченных элементов
Разновидности:
- Простые вставки
- Бинарные вставки
- Двухпутевые вставки
- Вставки в список
- Вставка в дерево
- Сортировка Шелла
- Сортировка с вычислением адреса и т. д.

29. Простые вставки

Алгоритм состоит из (n-1)-го прохода, каждый из
которых включает 4 действия:
• Взятие очередного i-го неотсортированного
элемента и сохранение его
• Поиск позиции j в отсортированной части массива, в
которой присутствие взятого элемента не нарушит
упорядоченности
• Сдвиг элементов от j-го до (i-1)-го вправо, чтобы
освободить позицию для вставки
• Вставка взятого элемента в найденную j-ую
позицию

30. Простые вставки

31. Простые вставки на Python

A = [7, 9, 8, 1, 5, 10, 12, 80]
N = len(A)
for i in range (1, len(A)):
t = A[i]
j=i-1
while (j >= 0 and t < A[j]):
A[j + 1] = A[j]
j=j-1
A[j + 1] = t
print(A)

32.

Простые вставки на Python
def insertion_sort(list1):
for i in range(1, len(list1)):
value = list1[i]
j=i-1
while j >= 0 and value < list1[j]:
list1[j + 1] = list1[j]
j -= 1
list1[j + 1] = value
return list1
list1 = [10, 5, 13, 8, 2]
print("The unsorted list is:", list1)
print("The sorted list1 is:", insertion_sort(list1))
Результат
The unsorted list is: [10, 5, 13, 8, 2]
The sorted list1 is: [2, 5, 8, 10, 13]

33. Простые вставки

34. Простые вставки

35. Вставки с барьерным элементом

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

36. Вставки с барьерным элементом

7
8
7
1
5
6
3
1
7
8
1
5
6
3
5
1
7
8
5
6
3
6
1
5
7
8
6
3
3
1
5
6
7
8
3
1
3
5
6
7
8

37. Вставки с барьерным элементом

38.

Вопросы для самостоятельной работы:
1. Назовите алгоритмы сортировки массивов
2. Какие сортировки относятся к
квадратичным сортировкам и почему они
называются квадратичными?
3. Принцип работы сортировки пузырьком.
4. Принцип работы шейкерной сортировки.
5. Принцип работы сортировки выбором.
6. Принцип работы сортировки вставкой
7. Виды сортировок вставкой.

39.

Основная Литература:
1. "Алгоритмы. Построение и анализ" авторы: Кормен Т., Лейзерсон Ч.,
Ривест Р., Штайн К. Издательство: Вильямс. Год выпуска: 2020. В главе 2
(с 38 по 71 страницы) описываются квадратичные сортировки
(сортировка пузырьком, сортировка выбором и сортировка вставками), а
в главе 7 (с 334 по 360 страницы) - сортировка слиянием.
2. "Algorithms and Data Structures in Action" автор: М. Джей.
Издательство: Manning Publications. Год выпуска: 2021. В главе 5 (с 165
по 192 страницы) описываются различные алгоритмы сортировки,
включая квадратичные сортировки (сортировка пузырьком, сортировка
выбором и сортировка вставками), а также быстрая сортировка и
сортировка слиянием.
Дополнительная литература:
1."Data Structures and Algorithms Made Easy: Data Structures and
Algorithmic Puzzles" автор: Нарасимха Каруманчи. Издательство:
CreateSpace Independent Publishing Platform. Год выпуска: 2019. В главе 8
(с 139 по 152 страницы) описываются квадратичные сортировки, а в
главе 9 (с 155 по 168 страницы) - сортировка слиянием.
2. "Algorithms Illuminated (Part 1): The Basics" автор: Тим Роугал.
Издательство: Soundlikeyourself Publishing. Год выпуска: 2017. В главе 7
(с 96 по 119 страницы) описываются различные алгоритмы сортировки.