Алгоритмы сортировки на массивах

Июль 26, 2022

Главная
Информатика
Алгоритмы сортировки на массивах

Содержание

2. Сортировка объектов Сортировка - в информатике переупорядочение рассматриваемых объектов по некоторому признаку или системе признаков Например,
3. Алгоритм сортировки АЛГОРИТМ ДЛЯ УПОРЯДОЧЕНИЯ НЕКОТОРОГО МНОЖЕСТВА ЭЛЕМЕНТОВ Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания множества
4. Классификация алгоритмов сортировок
5. Классификация алгоритмов сортировок Устойчивая сортировка не меняет взаимного расположения равных элементов
6. Классификация алгоритмов сортировок Естественность поведения – эффективность метода при обработке уже отсортированных, или частично отсортированных данных
7. Временная сложность сортировки – основной параметр, характеризующий быстродействие алгоритма Классификация алгоритмов сортировок Временная сложность сортировки –
8. Алгоритмы внешней и внутренней сортировки КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯ Алгоритмы внутренней сортировки оперируют сравнительно
9. КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯ Классификация алгоритмов сортировок
10. Оценка алгоритмов сортировки
11. Этапы алгоритма сортировки
12. Внутренняя сортировка
13. Простая вставка Бинарная вставка Простой выбор Стандартный обмен Метод Шелла Метод Хоара Турнирная Пирамидальная Внутренняя сортировка
14. Внутренняя сортировка Методы внутренней сортировки
15. Оценка сложности сортировки Постановка задачи сортировки в общем виде предполагает, что существуют только два типа действий
16. Простые сортировки К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных Иными
17. Сортировка Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора метод прямой
18. Последовательно просматривается массив и сравнивается каждая пара элементов между собой При этом "неправильное" расположение элементов устраняется
19. Отсортированная часть 13 6 2 10 8 Первый просмотр 6 13 8 13 13 2 10
20. 55 12 42 94 18 67 44 6 нет да да да да да да 55
21. Результаты работы алгоритма сортировки обменом
22. Сортировка обменом, метод пузырька Для осуществления сортировки нужно выполнить несколько шагов, несколько проходов по массиву На
23. Сортировка обменом, метод пузырька Следует обратить внимание на то, что за один проход в начальную часть
24. Сортировка обменом, метод пузырька На каждом шаге нужно организовать сравнение двух соседних элементов Так как сравнения
25. Метод пузырька, блок-схема Расположим массив сверху вниз, от нулевого элемента – к последнему Шаг сортировки состоит
26. Метод пузырька? Другая схема?
27. Суть сортировки: Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива Затем
28. На первом шаге ищется минимальный элемент во всем рассматриваемом массиве x[1] x[2] x[3] x[4] x[5] x[6]
29. x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43 55 82 42 94 18 6 63
30. x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43 55 82 42 94 18 6 63
31. x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43 55 82 42 94 18 6 63
32. x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43 55 82 42 94 18 6 63
33. 13 6 2 10 8 Min 2 Min 6 Min 8 13 Min 10 13 Отсортиро-ванная
34. Сортировка выбором / выделением Строим готовую последовательность, начиная с левого конца массива Алгоритм состоит из n-1
35. Сортировка прямыми вставками (прямым включением) Сортируемый массив разбивается на два участка: уже «готовый», упорядоченный и ещё
36. Сортировка прямыми вставками (прямым включением) Исходное положение: x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43
37. Сортировка прямыми вставками (прямым включением) 3 шаг 55 12 42 94 18 67 44 6 12
38. Сортировка прямыми вставками (прямым включением) Суть сортировки: Упорядочиваются два элемента массива Вставка третьего элемента в соответствующее
39. Сортировка прямыми вставками (прямым включением) 13 6 2 10 8 13 6 8 2 13 6
40. Сортировка прямыми вставками На i-м шаге последовательность разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n-1]
41. Сортировка прямыми вставками (прямым включением)
42. Анализ элементарных алгоритмов сортировок Замечания к определению временной сложности мерой объема входных данных служит количество элементов
43. Анализ сортировки обменом Количество сравнений - (n2-n)/2 Общее количество операций – Т(n2) Временная сложность алгоритма BubbleSort
44. Анализ сортировки обменом Для реализации алгоритма дополнительная память не требуется Временная сложность данного алгоритма практически не
45. Анализ сортировки выбором Количество сравнений - (n2-n)/2 Общее количество операций – Т(n2) Временная сложность алгоритма SelectSort
46. Анализ сортировки выбором Для реализации алгоритма дополнительная память не требуется Временная сложность данного алгоритма практически не
47. Анализ сортировки вставками Для массива 1 2 3 4 5 6 7 8 потребуется n-1 сравнение
48. Анализ сортировки вставками Для реализации алгоритма дополнительная память не требуется почти отсортированный массив будет досортирован очень
49. Анализ элементарных алгоритмов сортировок
50. Сравнение методов простой сортировки N – количество элементов, M – количество пересылок, C – количество сравнений
51. Выбор метода сортировки При сортировке небольших массивов (менее 100 элементов) лучше использовать метод «Всплывающего пузырька» Если
52. Сортировка вставкой Не эффективный метод, так как включение элемента связано со сдвигом всех предшествующих элементов на
53. Сортировка обменом Очень медленен и малоэффективен. На практике, даже с улучшениями, работает, слишком медленно, поэтому почти
55. Скачать презентацию

Слайд 2

Сортировка объектов
Сортировка - в информатике переупорядочение рассматриваемых объектов по некоторому признаку

или системе признаков
Например, упорядочение слов по алфавиту называется лексикографической сортировкой

Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы
К примеру, входные данные подаются "вперемешку", а вашей программе удобнее обрабатывать упорядоченную последовательность

Эта тема посвящена сугубо алгоритмической
проблеме упорядочения данных

Слайд 3

Алгоритм сортировки
АЛГОРИТМ ДЛЯ УПОРЯДОЧЕНИЯ НЕКОТОРОГО МНОЖЕСТВА ЭЛЕМЕНТОВ
Обычно под алгоритмом сортировки

подразумевают алгоритм упорядочивания множества элементов по возрастанию или убыванию
В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они располагаются рядом друг за другом в любом порядке. Однако иногда бывает полезно сохранять первоначальный порядок элементов с одинаковыми значениями
Часть данных используется в качестве ключа сортировки
Ключом сортировки называется атрибут , по значению которого определяется порядок элементов
При написании алгоритмов сортировок массивов следует учесть,
что ключ полностью или частично совпадает с данными

Слайд 4

Классификация алгоритмов сортировок

Слайд 5

Классификация алгоритмов сортировок
Устойчивая сортировка не меняет взаимного
расположения равных элементов

Слайд 6

Классификация алгоритмов сортировок
Естественность поведения – эффективность метода при обработке уже отсортированных,

или частично отсортированных данных
Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше

Слайд 7

Временная сложность сортировки – основной параметр, характеризующий быстродействие алгоритма
Классификация алгоритмов сортировок
Временная

сложность сортировки – основной параметр, характеризующий быстродействие алгоритма

Слайд 8

Алгоритмы внешней и внутренней сортировки
КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯ
Алгоритмы внутренней

сортировки оперируют сравнительно небольшими объемами данных.
Они могут "видеть" любой элемент сортируемого множества

Алгоритмы внешней сортировки применяются тогда, когда количество элементов велико и нет возможности "разложить их на столе"
(в оперативной памяти)

Слайд 9

КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯ
Классификация алгоритмов сортировок

Слайд 10

Оценка алгоритмов сортировки

Слайд 11

Этапы алгоритма сортировки

Слайд 12

Внутренняя сортировка

Слайд 13

Простая
вставка
Бинарная
вставка
Простой
выбор
Стандартный
обмен
Метод Шелла
Метод Хоара
Турнирная
Пирамидальная
Внутренняя сортировка

Слайд 14

Внутренняя сортировка
Методы внутренней сортировки

Слайд 15

Оценка сложности сортировки
Постановка задачи сортировки в общем виде предполагает, что

существуют только два типа действий с данными сортируемого типа:
сравнение двух элементов (x пересылка элемента (x:=y)
Поэтому удобная мера сложности алгоритма сортировки массива a[1..n]:
по времени – количество сравнений C(n)
количество пересылок M(n)

Слайд 16

Простые сортировки
К простым внутренним сортировкам относят методы, сложность которых пропорциональна

квадрату размерности входных данных
Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N2 действий, где С - некоторая константа. Этот факт принято обозначать следующей символикой: O(N2)

Слайд 17

Сортировка
Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
метод прямой

вставки
сложные, но эффективные
«быстрая сортировка» (Quick Sort)
сортировка «кучей» (Heap Sort)
сортировка слиянием
пирамидальная сортировка

сложность O(N2)

сложность O(N·logN)

НЕ СУЩЕСТВУЕТ УНИВЕРСАЛЬНОГО, НАИБОЛЕЕ ЭФФЕКТИВНОГО СПОСОБА СОРТИРОВКИ

Слайд 18

Последовательно просматривается массив и сравнивается каждая пара элементов между собой
При этом

"неправильное" расположение элементов устраняется путем их перестановки
Процесс просмотра и сравнения элементов повторяется до просмотра
всего массива

Метод пузырька (сортировка обменом)

Слайд 19

Отсортированная часть
13
6
2
10
8
Первый просмотр
6
13
8
13
13
2
10
13
Второй просмотр
6
8
2
8
Третий просмотр
6
2
6
Четвертый просмотр
2
6<13
8<13
2<13
10<13
Отсортиро-ванная часть
Отсортированная часть
Массив отсортирован
по возрастанию
6<8
8>2
8<10
6>2
6<8
6>2
по

возрастанию

Метод пузырька / сортировка обменом

Слайд 20

55
12
42
94
18
67
44
6
нет
да
да
да
да
да
да
55
12
42
94
18
67
44
6
нет
да
да
нет
да
да
55
12
42
94
18
67
44
6
55
12
42
94
18
67
44
6
55
12
42
94
18
67
44
6

Слайд 21

Результаты работы алгоритма сортировки обменом

Слайд 22

Сортировка обменом, метод пузырька
Для осуществления сортировки нужно выполнить несколько шагов, несколько

проходов по массиву

На первом шаге на своем месте оказывается самый маленький элемент. На втором ― следующий по величине и т.д.
Вообще, на каждом шаге на «свое место» попадает, по крайней мере, один элемент массива
Для полного упорядочения нужно выполнить N-1 шаг сортировки

Так как при вертикальном расположении массива на каждом проходе в начальную часть массива, наверх «поднимаются», «всплывают» маленькие, «лёгкие» элементы, то обсуждаемый тип сортировки называют «пузырьковой», по аналогии с всплывающими к поверхности воды пузырьками воздуха

Слайд 23

Сортировка обменом, метод пузырька
Следует обратить внимание на то, что за один

проход в начальную часть массива (в его уже упорядоченную часть) попадает самый маленький элемент из неупорядоченной части, а самый большой элемент перемещается в конец массива, «опускается вниз» всего на одну позицию

В методе обменной сортировки нужный элемент отыскивается с помощью действий в неупорядоченной части и найденный элемент добавляется в конец уже упорядоченной части

Слайд 24

Сортировка обменом, метод пузырька
На каждом шаге нужно организовать сравнение двух соседних

элементов
Так как сравнения начинают с последней пары элементов, то сначала сравниваются N-1-й и N-й элементы, затем N-2-й и N-1-й элементы и т.д., последними на первом проходе сравниваются 2 и 1 элементы

Пару сравниваемых элементов можно задавать меньшим или большим номером из номеров, образующих пару элементов

Если у сравниваемых элементов x[j] и x[j-1] обнаруживается «неправильный» порядок, то они стандартным способом меняются местами

Слайд 25

Метод пузырька, блок-схема
Расположим массив сверху вниз, от нулевого элемента – к

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

Слайд 26

Метод пузырька? Другая схема?

Слайд 27

Суть сортировки:
Выбирается элемент с наименьшим значением и делается его обмен с

первым элементом массива
Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов

Сортировка выбором / выделением

Слайд 28

На первом шаге ищется минимальный элемент во всем рассматриваемом массиве

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]

В данном случае это x[7]=6. Чтобы массив был упорядоченным этот элемент должен стоять на первом месте. Поэтому, совершим обмен значениями между найденным и начальным элементом массива

Сортировка выбором / выделением

Слайд 29

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]
43
55
82
42
94
18
6
63
6
43
Наименьший элемент

уже стоит на месте, поэтому в дальнейшем можно рас-сматривать уже не весь массив, а только его часть, начинающуюся со второго элемента

На втором шаге ищется минимальный элемент в части массива, начинающейся со второго элемента. В данном примере это x[6]=18. И менять шестой элемент нужно с начальным элементом рассматриваемого участка массива, то есть со вторым элементом массива.

Теперь уже два элемента стоят на своих местах

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]

Сортировка выбором / выделением

Слайд 30

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]
43
55
82
42
94
18
6
63
6
43
18
55
Третий шаг.

Минимальный элемент x[4]=42

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]

Четвертый шаг. Минимальный элемент x[7]=43

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]

Сортировка выбором / выделением

Слайд 31

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]
43
55
82
42
94
18
6
63
6
43
18
55
42
82
43
82
Пятый шаг.

Минимальный элемент x[6]=55

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]

Шестой шаг. Минимальный элемент x[8]=63

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]

Сортировка выбором / выделением

Слайд 32

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]
43
55
82
42
94
18
6
63
6
43
18
55
42
82
43
82
55
94
63
94
Седьмой шаг.

Минимальный элемент x[7]=82

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]

Массив упорядочен

Сущность выполняемых действий
Сортируемый массив разбивается на два участка: уже «готовый», упорядоченный и ещё неупорядоченный. На каждом шаге сортировки путем перебора неупорядоченного участка выбирается один элемент и включается в конец уже упорядоченного участка

Сортировка выбором / выделением

Слайд 33

13
6
2
10
8
Min
2
Min
6
Min
8
13
Min
10
13
Отсортиро-ванная часть
Отсортированная часть
Отсортированная часть
Массив отсортирован по возрастанию
по возрастанию
Сортировка выбором / выделением

Слайд 34

Сортировка выбором / выделением
Строим готовую последовательность, начиная с левого конца массива
Алгоритм

состоит из n-1 последовательных шагов, начиная от нулевого и заканчивая (n-2)-м
На i-м шаге выбираем наименьший из элементов a[i] ... a[n-1] и меняем его местами с a[i]

Слайд 35

Сортировка прямыми вставками (прямым включением)
Сортируемый массив разбивается на два участка: уже

«готовый», упорядоченный и ещё неупорядоченный
На каждом шаге берётся первый элемент из неупорядоченной части и вставляется в подходящее место в уже упорядоченной части, которое подбирается путём перебора её элементов

В чём принципиальное различие между методом выбора и методом включения?

Способ определения места вставки - место ищется в уже упорядоченной части массива
Её элементы, начиная с последнего, по очереди сравниваются с элементом, для которого ищется место
Как только очередной элемент упорядоченной части оказывается меньше, чем новый элемент (сортировка по возрастанию), место вставки найдено.

Слайд 36

Сортировка прямыми вставками (прямым включением)
Исходное положение:
x[1] x[2] x[3] x[4] x[5]

x[6] x[7] x[8]

1 шаг

Упорядоченная часть

Неупорядоченная часть

2 шаг

< ?

Слайд 37

Сортировка прямыми вставками (прямым включением)
3 шаг
55
12
42
94
18
67
44
6
12
55
42
94
18
67
44
6
< ?
< ?
44
55
42
94
18
67
12
6
4 шаг
42
44
55
94
18
67
12
6
< ?
< ?
<

Слайд 38

Сортировка прямыми вставками (прямым включением)
Суть сортировки:
Упорядочиваются два элемента массива
Вставка третьего элемента

в соответствующее место по отношению к первым двум элементам
Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены

Слайд 39

Сортировка прямыми вставками (прямым включением)
13
6
2
10
8
13
6
8
2
13
6
8
8
13
13
10
6<13
8>6 8<13
2<6 2<8 2<13
10<13
Массив отсортирован по возрастанию
по

возрастанию

Слайд 40

Сортировка прямыми вставками
На i-м шаге последовательность разделена на две части: готовую

a[0]...a[i] и неупорядоченную a[i+1]...a[n-1]
На (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива
Поиск подходящего места для элемента осуществляется путем сравнений с элементом, стоящим перед ним
В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется

Слайд 41

Сортировка прямыми вставками (прямым включением)

Слайд 42

Анализ элементарных алгоритмов сортировок
Замечания к определению временной сложности
мерой объема входных данных

служит количество элементов n, подлежащих сортировке
время работы программы сортировки может зависеть не только от количества сортируемых элементов, но и от их исходной упорядоченности, два крайних случая :
сортируемый массив уже является упорядоченным как требуется - лучший случай исходных данных
массив упорядочен в обратной последовательности - худший случай
основными операциями сортировки являются сравнения элементов и их перестановка

Слайд 43

Анализ сортировки обменом
Количество сравнений - (n2-n)/2
Общее количество операций – Т(n2)
Временная сложность

алгоритма BubbleSort
имеет порядок О(n2)

Слайд 44

Анализ сортировки обменом
Для реализации алгоритма дополнительная память
не требуется
Временная сложность данного

алгоритма практически не зависит от начальной упорядоченности массива, его
поведение можно считать не естественным
Обмен не затрагивает элементы с одинаковыми значениями ключа, ранее стоящие равные элементы "всплывут" к началу последовательности раньше последующих; их естественный порядок следования не изменится, следовательно, сортировка обменом устойчива

Слайд 45

Анализ сортировки выбором
Количество сравнений - (n2-n)/2
Общее количество операций – Т(n2)
Временная сложность

алгоритма SelectSort
имеет порядок О(n2)

Слайд 46

Анализ сортировки выбором
Для реализации алгоритма дополнительная память
не требуется
Временная сложность данного

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

Слайд 47

Анализ сортировки вставками
Для массива 1 2 3 4 5 6 7

8 потребуется n-1 сравнение
Для массива 8 7 6 5 4 3 2 1 потребуется (n2-n)/2 сравнений
Вывод: Общее количество операций – Т(n2)
Временная сложность алгоритма InsertSort
имеет верхний порядок роста О(n2) и
нижний порядок роста Ω(n)

Слайд 48

Анализ сортировки вставками
Для реализации алгоритма дополнительная память
не требуется
почти отсортированный массив

будет досортирован очень быстро - поведение можно считать естественным
элементы с равными ключами продвигаются на свои места в отсортированной последовательности в естественном порядке –
этот вид сортировки устойчив

Слайд 49

Анализ элементарных алгоритмов сортировок

Слайд 50

Сравнение методов простой сортировки
N – количество элементов,
M – количество пересылок,

C – количество сравнений

Слайд 51

Выбор метода сортировки
При сортировке небольших массивов (менее 100 элементов) лучше использовать

метод «Всплывающего пузырька»
Если известно, что список уже почти отсортирован, то подойдет любой метод

вставка выбор обмен

Слайд 52

Сортировка вставкой
Не эффективный метод, так как включение элемента связано со сдвигом

всех предшествующих элементов на одну позицию, а эта операция неэкономна

В совокупности устойчивость и естественность поведения алгоритма, делает метод хорошим выбором в соответствующих ситуациях

Слайд 53

Сортировка обменом
Очень медленен и малоэффективен.
На практике, даже с улучшениями, работает,

слишком медленно, поэтому почти не применяется

Прост, и его можно улучшать

Алгоритмы сортировки на массивах

Содержание

Сортировка объектов Сортировка - в информатике переупорядочение рассматриваемых объектов по некоторому признаку

Алгоритм сортировки АЛГОРИТМ ДЛЯ УПОРЯДОЧЕНИЯ НЕКОТОРОГО МНОЖЕСТВА ЭЛЕМЕНТОВОбычно под алгоритмом сортировки

Классификация алгоритмов сортировок

Классификация алгоритмов сортировокУстойчивая сортировка не меняет взаимного расположения равных элементов

Классификация алгоритмов сортировокЕстественность поведения – эффективность метода при обработке уже отсортированных,

Временная сложность сортировки – основной параметр, характеризующий быстродействие алгоритмаКлассификация алгоритмов сортировокВременная

Алгоритмы внешней и внутренней сортировкиКЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯАлгоритмы внутренней

КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯКлассификация алгоритмов сортировок

Оценка алгоритмов сортировки

Этапы алгоритма сортировки

Внутренняя сортировка

Простая вставкаБинарнаявставкаПростой выборСтандартныйобменМетод ШеллаМетод ХоараТурнирнаяПирамидальнаяВнутренняя сортировка

Внутренняя сортировка Методы внутренней сортировки

Оценка сложности сортировки Постановка задачи сортировки в общем виде предполагает, что

Простые сортировки К простым внутренним сортировкам относят методы, сложность которых пропорциональна

Сортировка Алгоритмы:простые и понятные, но неэффективные для больших массивовметод пузырькаметод выбораметод прямой

Последовательно просматривается массив и сравнивается каждая пара элементов между собойПри этом

551242941867446нетдададададада551242941867446нетдаданетдада551242941867446551242941867446551242941867446

Результаты работы алгоритма сортировки обменом

Сортировка обменом, метод пузырькаДля осуществления сортировки нужно выполнить несколько шагов, несколько

Сортировка обменом, метод пузырькаСледует обратить внимание на то, что за один

Сортировка обменом, метод пузырькаНа каждом шаге нужно организовать сравнение двух соседних

Метод пузырька, блок-схема Расположим массив сверху вниз, от нулевого элемента – к

Метод пузырька? Другая схема?

Суть сортировки:Выбирается элемент с наименьшим значением и делается его обмен с

На первом шаге ищется минимальный элемент во всем рассматриваемом массиве

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 435582429418663643Наименьший элемент

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 4355824294186636431855Третий шаг.

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 435582429418663643185542824382Пятый шаг.

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43558242941866364318554282438255946394Седьмой шаг.

Сортировка выбором / выделением Строим готовую последовательность, начиная с левого конца массиваАлгоритм

Сортировка прямыми вставками (прямым включением)Сортируемый массив разбивается на два участка: уже

Сортировка прямыми вставками (прямым включением)Исходное положение: x[1] x[2] x[3] x[4] x[5]

Сортировка прямыми вставками (прямым включением)3 шаг551242941867446125542941867446< ?< ?4455429418671264 шаг424455941867126< ?< ?<

Сортировка прямыми вставками (прямым включением)Суть сортировки:Упорядочиваются два элемента массиваВставка третьего элемента

Сортировка прямыми вставками (прямым включением)136210813682136881313106<138>6 8<132<6 2<8 2<1310<13Массив отсортирован по возрастаниюпо

Сортировка прямыми вставками На i-м шаге последовательность разделена на две части: готовую

Сортировка прямыми вставками (прямым включением)

Анализ элементарных алгоритмов сортировокЗамечания к определению временной сложностимерой объема входных данных

Анализ сортировки обменом Количество сравнений - (n2-n)/2Общее количество операций – Т(n2)Временная сложность

Анализ сортировки обменом Для реализации алгоритма дополнительная память не требуетсяВременная сложность данного

Анализ сортировки выбором Количество сравнений - (n2-n)/2Общее количество операций – Т(n2)Временная сложность

Анализ сортировки выбором Для реализации алгоритма дополнительная память не требуетсяВременная сложность данного

Анализ сортировки вставками Для массива 1 2 3 4 5 6 7

Анализ сортировки вставками Для реализации алгоритма дополнительная память не требуетсяпочти отсортированный массив

Анализ элементарных алгоритмов сортировок

Сравнение методов простой сортировкиN – количество элементов, M – количество пересылок,

Выбор метода сортировки При сортировке небольших массивов (менее 100 элементов) лучше использовать

Сортировка вставкой Не эффективный метод, так как включение элемента связано со сдвигом

Сортировка обменом Очень медленен и малоэффективен. На практике, даже с улучшениями, работает,

Похожие презентации

Сортировка объектов
Сортировка - в информатике переупорядочение рассматриваемых объектов по некоторому признаку

Алгоритм сортировки
АЛГОРИТМ ДЛЯ УПОРЯДОЧЕНИЯ НЕКОТОРОГО МНОЖЕСТВА ЭЛЕМЕНТОВ
Обычно под алгоритмом сортировки

Классификация алгоритмов сортировок
Устойчивая сортировка не меняет взаимного
расположения равных элементов

Классификация алгоритмов сортировок
Естественность поведения – эффективность метода при обработке уже отсортированных,

Временная сложность сортировки – основной параметр, характеризующий быстродействие алгоритма
Классификация алгоритмов сортировок
Временная

Алгоритмы внешней и внутренней сортировки
КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯ
Алгоритмы внутренней

КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ ПО СФЕРЕ ПРИМЕНЕНИЯ
Классификация алгоритмов сортировок

Простая
вставка
Бинарная
вставка
Простой
выбор
Стандартный
обмен
Метод Шелла
Метод Хоара
Турнирная
Пирамидальная
Внутренняя сортировка

Внутренняя сортировка
Методы внутренней сортировки

Оценка сложности сортировки
Постановка задачи сортировки в общем виде предполагает, что

Простые сортировки
К простым внутренним сортировкам относят методы, сложность которых пропорциональна

Сортировка
Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
метод прямой

Последовательно просматривается массив и сравнивается каждая пара элементов между собой
При этом

55
12
42
94
18
67
44
6
нет
да
да
да
да
да
да
55
12
42
94
18
67
44
6
нет
да
да
нет
да
да
55
12
42
94
18
67
44
6
55
12
42
94
18
67
44
6
55
12
42
94
18
67
44
6

Сортировка обменом, метод пузырька
Для осуществления сортировки нужно выполнить несколько шагов, несколько

Сортировка обменом, метод пузырька
Следует обратить внимание на то, что за один

Сортировка обменом, метод пузырька
На каждом шаге нужно организовать сравнение двух соседних

Метод пузырька, блок-схема
Расположим массив сверху вниз, от нулевого элемента – к

Суть сортировки:
Выбирается элемент с наименьшим значением и делается его обмен с

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]
43
55
82
42
94
18
6
63
6
43
Наименьший элемент

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]
43
55
82
42
94
18
6
63
6
43
18
55
Третий шаг.

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]
43
55
82
42
94
18
6
63
6
43
18
55
42
82
43
82
Пятый шаг.

x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8]
43
55
82
42
94
18
6
63
6
43
18
55
42
82
43
82
55
94
63
94
Седьмой шаг.

Сортировка выбором / выделением
Строим готовую последовательность, начиная с левого конца массива
Алгоритм

Сортировка прямыми вставками (прямым включением)
Сортируемый массив разбивается на два участка: уже

Сортировка прямыми вставками (прямым включением)
Исходное положение:
x[1] x[2] x[3] x[4] x[5]

Сортировка прямыми вставками (прямым включением)
3 шаг
55
12
42
94
18
67
44
6
12
55
42
94
18
67
44
6
< ?
< ?
44
55
42
94
18
67
12
6
4 шаг
42
44
55
94
18
67
12
6
< ?
< ?
<

Сортировка прямыми вставками (прямым включением)
Суть сортировки:
Упорядочиваются два элемента массива
Вставка третьего элемента

Сортировка прямыми вставками (прямым включением)
13
6
2
10
8
13
6
8
2
13
6
8
8
13
13
10
6<13
8>6 8<13
2<6 2<8 2<13
10<13
Массив отсортирован по возрастанию
по

Сортировка прямыми вставками
На i-м шаге последовательность разделена на две части: готовую

Анализ элементарных алгоритмов сортировок
Замечания к определению временной сложности
мерой объема входных данных

Анализ сортировки обменом
Количество сравнений - (n2-n)/2
Общее количество операций – Т(n2)
Временная сложность

Анализ сортировки обменом
Для реализации алгоритма дополнительная память
не требуется
Временная сложность данного

Анализ сортировки выбором
Количество сравнений - (n2-n)/2
Общее количество операций – Т(n2)
Временная сложность

Анализ сортировки выбором
Для реализации алгоритма дополнительная память
не требуется
Временная сложность данного

Анализ сортировки вставками
Для массива 1 2 3 4 5 6 7

Анализ сортировки вставками
Для реализации алгоритма дополнительная память
не требуется
почти отсортированный массив

Сравнение методов простой сортировки
N – количество элементов,
M – количество пересылок,

Выбор метода сортировки
При сортировке небольших массивов (менее 100 элементов) лучше использовать

Сортировка вставкой
Не эффективный метод, так как включение элемента связано со сдвигом

Сортировка обменом
Очень медленен и малоэффективен.
На практике, даже с улучшениями, работает,