- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Методы сортировки данных
Содержание
- 2. Сортировка объектов – расположение объектов по возрастанию или убыванию согласно определенному линейному отношению порядка
- 3. Сортировка объектов:ВнутренняяВнешняя
- 4. Внутренняя сортировка оперирует с массивами, целиком помещающимися
- 6. Алгоритм сортировки вставкой
- 7. Суть сортировки: Упорядочиваются два элемента массиваВставка третьего
- 8. Сортировка вставкой1362108136821368813131066 8
- 9. Пусть нужно отсортировать массив А по возрастанию,
- 10. Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j=2
- 11. Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j=2
- 12. Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j=2
- 13. Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j=2
- 14. Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j=2
- 15. Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j=2
- 16. Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j=2
- 17. Алгоритм сортировки выбором
- 18. Суть сортировки:Выбирается элемент с наименьшим значением и
- 19. 1362108Сортировка выборомMin2Min6Min813Min1013Отсортиро-ванная частьОтсортированная частьОтсортированная частьМассив отсортирован по возрастаниюпо возрастанию
- 20. Постановка задачиПусть нужно отсортировать массив А по
- 21. Начало алгоритма.Шаг 1 j:=1,Шаг 2 Пока j
- 22. Начало алгоритма.Шаг 1 j:=1,Шаг 2 Пока j
- 23. Начало алгоритма.Шаг 1 j:=1,Шаг 2 Пока j
- 24. Алгоритм сортировки обменом («пузырьковая»)
- 25. Суть сортировки:Последовательно просматривается массив и сравнивается каждая
- 26. Сортировка обменом1362108Первый просмотр6138131321013Второй просмотр6828Третий просмотр626Четвертый просмотр26
- 27. Пусть нужно отсортировать массив А по возрастанию,
- 28. Начало алгоритма.Шаг 1 j:=N,Шаг 2 Пока j>=2
- 29. Начало алгоритма.Шаг 1 j:=N,Шаг 2 Пока j>=2
- 30. Начало алгоритма.Шаг 1 j:=N,Шаг 2 Пока j>=2
- 31. Алгоритм сортировки Шелла
- 32. Классифицируется как «слияние вставкой»;Называется «сортировкой с убывающим
- 33. Условия реализации:Конкретная последовательность шагов может быть другой,
- 34. Суть сортировки:Сначала сортируются все элементы, отстоящие друг
- 35. 12Сортировка Шелла814641234121 шаг. 4 группы из 2-х элементов1734124899114762 шаг. 2 группы из 4-х элементов1212121241684
- 36. Сортировка Шелла4163 шаг. 1 группа из 8-ми элементовМассив отсортирован по возрастаниюпо возрастанию121498714641
- 37. Пусть нужно отсортировать массив А по возрастанию,
- 38. Начало алгоритма.Шаг 1. M=целая часть N/2Шаг 2.
- 39. Начало алгоритма.Шаг 1. M=целая часть N/2Шаг 2.
- 40. Зачем необходимо это действие?Начало алгоритма.Шаг 1. M=целая
- 41. Зачем необходимо это действие?Начало алгоритма.Шаг 1. M=целая
- 42. Почему условие выхода из цикла такое?Начало алгоритма.Шаг
- 43. Алгоритм быстрой сортировки
- 44. Придумана Ч.А.Р. Хоаром (Charles Antony Richard Hoare);В основе – сортировка обменами;Основана на делении массива
- 45. Суть сортировки:Выбирается некоторое значение (x)- барьерный элемент,
- 46. Суть сортировки: Меняем найденные элементы местами. В
- 47. Быстрая сортировка812371911416Барьерный элемент43781234Барьерный элемент8121119Барьерный элемент121916198>7 переносим в
- 48. Пусть нужно отсортировать массив А по возрастанию,
- 49. Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i
- 50. Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i
- 51. Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i
- 52. Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i
- 53. Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i
- 54. Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i
- 55. Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i
- 56. Основывается:количестве необходимых сравнений количестве пересылокОценка эффективности
- 57. Параметры оценки алгоритмов Время сортировки - основной
- 58. Устойчивость – отсортированный массив не меняет порядок
- 59. Естественность поведения - эффективность метода при
- 60. Оценка алгоритма сортировки выбором Общее количество сравнений
- 61. Устойчив ли этот метод?Не устойчив
- 62. Если входная последовательность почти упорядочена, то сравнений будет столько жеалгоритм ведет себя неестественно
- 63. Оценка алгоритма сортировки вставкой Для массива 1
- 64. Устойчив ли этот метод?Устойчивпорядок элементов с одинаковыми ключами не изменяется
- 65. Наименьшие оценки эффективности, когда элементы предварительно упорядочены,
- 66. Не эффективный метод, так как включение элемента
- 67. Оценка алгоритма сортировки обменом Количество сравнений (n2-n)/2Общее количество операцийTheta(n2)
- 68. Ответьте на следующие вопросы:Устойчив ли этот метод?Естественное ли поведение этого алгоритма?
- 69. Очень медленен и малоэффективен. На практике, даже
- 70. Сравнение методов простой сортировкиN – количество элементов,
- 71. Выбор метода сортировкиПри сортировке маленьких массивов (менее
- 72. Оценка алгоритма Шелла Время выполнения пропорционально n1.2,
- 73. Оценка алгоритма быстрой сортировки Если размер массива
- 74. Общее количество операций Theta(n). Количество шагов деления
- 75. Метод неустойчив. Поведение довольно естественно, если учесть,
- 76. Итоги:Предпочтительным является метод прямого включения;Сортировка методом простого обмена является наихудшей;Быстрая сортировка превосходит все остальные методы сортировки;
- 77. Контрольные вопросыЧто такое «сортировка»?В чем заключается метод
- 78. Скачать презентацию
- 79. Похожие презентации
Сортировка объектов – расположение объектов по возрастанию или убыванию согласно определенному линейному отношению порядка
![Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i](/img/tmb/14/1363157/2622f417b69807a78f69dfc9dc491848-720x.jpg "Методы сортировки данных")
![Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i](/img/tmb/14/1363157/7ba5e720bfb98a5a0db48faaa1b6d46a-720x.jpg "Методы сортировки данных")
![Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i](/img/tmb/14/1363157/69929af53c4e281bb6a8856418169549-720x.jpg "Методы сортировки данных")
![Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i](/img/tmb/14/1363157/7a175fa3893f69f9bc2a972d07d53999-720x.jpg "Методы сортировки данных")
![Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i](/img/tmb/14/1363157/df2541a2bfb10321394ddbb57a1c1933-720x.jpg "Методы сортировки данных")
![Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i](/img/tmb/14/1363157/1fb237bdc39a621e357e869fde1d1e2e-720x.jpg "Методы сортировки данных")
![Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i](/img/tmb/14/1363157/d834f19ef96d37a0c40f756ae71b3174-720x.jpg "Методы сортировки данных")
Слайд 2 Сортировка объектов – расположение объектов по возрастанию или
убыванию согласно определенному линейному отношению порядка
Слайд 4 Внутренняя сортировка оперирует с массивами, целиком помещающимися в
оперативной памяти с произвольным доступом к любой ячейке.
Данные
обычно сортируются на том же месте, без дополнительных затрат
Слайд 7
Суть сортировки:
Упорядочиваются два элемента массива
Вставка третьего элемента
в соответствующее место по отношению к первым двум элементам.
Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.
Слайд 9 Пусть нужно отсортировать массив А по возрастанию, в
котором N элементов методом вставки
Вспомогательные переменные
j – номер первого
элемента остатка.i – номер перемещаемого элемента.
f – условие выхода из цикла (если f=1, то выход)
Val – промежуточное значение, используемое для перемещения элементов массив
Постановка задачи
Слайд 10
Начало алгоритма.
Шаг 1 j:=2,
Шаг 2 Пока j
2.1 i:=j; f:=0,
Шаг 2.2 Пока i>=2 и f=0 выполнять:
Шаг
2.2.1 Если A[i-1]>A[i]то Val:=A[i-1];
A[i-1]:=A[i];
A[i]:=Val,
иначе f:=1,
Шаг 2.2.2 i:=i-1,
Шаг 2.3 j:=j+1.
Конец алгоритма.
Слайд 11
Начало алгоритма.
Шаг 1 j:=2,
Шаг 2 Пока j
2.1 i:=j; f:=0,
Шаг 2.2 Пока i>=2 и f=0 выполнять:
Шаг
2.2.1 Если A[i-1]>A[i]то Val:=A[i-1];
A[i-1]:=A[i];
A[i]:=Val,
иначе f:=1,
Шаг 2.2.2 i:=i-1,
Шаг 2.3 j:=j+1.
Конец алгоритма.
Что обозначает данное условие?
Слайд 12
Начало алгоритма.
Шаг 1 j:=2,
Шаг 2 Пока j
2.1 i:=j; f:=0,
Шаг 2.2 Пока i>=2 и f=0 выполнять:
Шаг
2.2.1 Если A[i-1]>A[i]то Val:=A[i-1];
A[i-1]:=A[i];
A[i]:=Val,
иначе f:=1,
Шаг 2.2.2 i:=i-1,
Шаг 2.3 j:=j+1.
Конец алгоритма.
Почему стартовое значение j =2 ?
Слайд 13
Начало алгоритма.
Шаг 1 j:=2,
Шаг 2 Пока j
2.1 i:=j; f:=0,
Шаг 2.2 Пока i>=2 и f=0 выполнять:
Шаг
2.2.1 Если A[i-1]>A[i]то Val:=A[i-1];
A[i-1]:=A[i];
A[i]:=Val,
иначе f:=1,
Шаг 2.2.2 i:=i-1,
Шаг 2.3 j:=j+1.
Конец алгоритма.
Почему стартовое значение i =2 ?
Слайд 14
Начало алгоритма.
Шаг 1 j:=2,
Шаг 2 Пока j
2.1 i:=j; f:=0,
Шаг 2.2 Пока i>=2 и f=0 выполнять:
Шаг
2.2.1 Если A[i-1]>A[i]то Val:=A[i-1];
A[i-1]:=A[i];
A[i]:=Val,
иначе f:=1,
Шаг 2.2.2 i:=i-1,
Шаг 2.3 j:=j+1.
Конец алгоритма.
Всегда ли происходит обмен входного j элемента
с отсортированным элементом ?
Слайд 15
Начало алгоритма.
Шаг 1 j:=2,
Шаг 2 Пока j
2.1 i:=j; f:=0,
Шаг 2.2 Пока i>=2 и f=0 выполнять:
Шаг
2.2.1 Если A[i-1]>A[i]то Val:=A[i-1];
A[i-1]:=A[i];
A[i]:=Val,
иначе f:=1,
Шаг 2.2.2 i:=i-1,
Шаг 2.3 j:=j+1.
Конец алгоритма.
Возможно ли заменить цикл ПОКА и ЕСЛИ
одним циклом ПОКА с условием i>=2 и A[i-1]>A[i] ?
Слайд 16
Начало алгоритма.
Шаг 1 j:=2,
Шаг 2 Пока j
2.1 i:=j; f:=0,
Шаг 2.2 Пока i>=2 и f=0 выполнять:
Шаг
2.2.1 Если A[i-1]>A[i]то Val:=A[i-1];
A[i-1]:=A[i];
A[i]:=Val,
иначе f:=1,
Шаг 2.2.2 i:=i-1,
Шаг 2.3 j:=j+1.
Конец алгоритма.
Для чего нужен этот оператор?
Слайд 18
Суть сортировки:
Выбирается элемент с наименьшим значением и делается
его обмен с первым элементом массива.
Затем находится элемент
с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.
Слайд 19
13
6
2
10
8
Сортировка выбором
Min
2
Min
6
Min
8
13
Min
10
13
Отсортиро-ванная часть
Отсортированная часть
Отсортированная часть
Массив отсортирован по возрастанию
по
возрастанию
Слайд 20
Постановка задачи
Пусть нужно отсортировать массив А по возрастанию,
в котором N элементов методом выбора.
Вспомогательные переменные
j –
номер первого элемента остатка.i – номер перемещаемого элемента.
min – минимальное число в массиве.
Imin – номер минимального числа в массиве
Слайд 21
Начало алгоритма.
Шаг 1 j:=1,
Шаг 2 Пока j
Шаг 2.1 min:=a[j], Imin:=j, i:=j+1
Шаг 2.2
Пока i<=N выполнять:Шаг 2.2.1 Если A[i]
Шаг 2.2.2 i:=i+1,
Шаг 2.3 A[Imin]:=A[j], A[j]:=min
Шаг 2.4 j:=j+1.
Конец алгоритма.
Слайд 22
Начало алгоритма.
Шаг 1 j:=1,
Шаг 2 Пока j
Шаг 2.1 min:=a[j], Imin:=j, i:=j+1
Шаг 2.2
Пока i<=N выполнять:Шаг 2.2.1 Если A[i]
Шаг 2.2.2 i:=i+1,
Шаг 2.3 A[Imin]:=A[j], A[j]:=min
Шаг 2.4 j:=j+1.
Конец алгоритма.
Что происходит в выделенном фрагменте?
Слайд 23
Начало алгоритма.
Шаг 1 j:=1,
Шаг 2 Пока j
Шаг 2.1 min:=a[j], Imin:=j, i:=j+1
Шаг 2.2
Пока i<=N выполнять:Шаг 2.2.1 Если A[i]
Шаг 2.2.2 i:=i+1,
Шаг 2.3 A[Imin]:=A[j], A[j]:=min
Шаг 2.4 j:=j+1.
Конец алгоритма.
Что происходит в выделенном фрагменте?
Слайд 25
Суть сортировки:
Последовательно просматривается массив и сравнивается каждая пара
элементов между собой.
При этом "неправильное" расположение элементов устраняется
путем их перестановки. Процесс просмотра и сравнения элементов повторяется до просмотра всего массива.
Слайд 26
Сортировка обменом
13
6
2
10
8
Первый просмотр
6
13
8
13
13
2
10
13
Второй просмотр
6
8
2
8
Третий просмотр
6
2
6
Четвертый просмотр
2
6
часть
Массив отсортирован по возрастанию
62
82
62
по возрастанию
Слайд 27 Пусть нужно отсортировать массив А по возрастанию, в
котором N элементов методом обмена
Вспомогательные переменные
j – номер первого
элемента остатка.i – номер перемещаемого элемента.
Val – промежуточное значение, используемое для перемещения элементов массива
Постановка задачи
Слайд 28
Начало алгоритма.
Шаг 1 j:=N,
Шаг 2 Пока j>=2 выполнять:
Шаг
2.1 i:=1; ,
Шаг 2.2 Пока iA[i+1]
то Val:=A[i]; A[i]:=A[i+1];
A[i+1]:=Val,
Шаг 2.2.2 i=i+1,
Шаг 2.3 j:=j-1.
Конец алгоритма.
Сравнение соседних элементов
Обмен соседних элементов местами, в случае если левый больше правого
Формируется отсортированная часть
Слайд 29
Начало алгоритма.
Шаг 1 j:=N,
Шаг 2 Пока j>=2 выполнять:
Шаг
2.1 i:=1; ,
Шаг 2.2 Пока iA[i+1]
то Val:=A[i]; A[i]:=A[i+1];
A[i+1]:=Val,
Шаг 2.2.2 i=i+1,
Шаг 2.3 j:=j-1.
Конец алгоритма.
Почему условие такое?
Слайд 30
Начало алгоритма.
Шаг 1 j:=N,
Шаг 2 Пока j>=2 выполнять:
Шаг
2.1 i:=1; ,
Шаг 2.2 Пока iA[i+1]
то Val:=A[i]; A[i]:=A[i+1];
A[i+1]:=Val,
Шаг 2.2.2 i=i+1,
Шаг 2.3 j:=j-1.
Конец алгоритма.
Почему значение j уменьшается?
Можно ли увеличивать? Что нужно изменить?
Слайд 32
Классифицируется как «слияние вставкой»;
Называется «сортировкой с убывающим шагом»
Общий
метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния
между сравниваемыми элементами
Слайд 33
Условия реализации:
Конкретная последовательность шагов может быть другой, но
последний шаг должен быть равен 1;
Следует избегать последовательность, которые
являются степенями 2 (т.е. нельзя использовать последовательность шагов – 4,2)?
?
Слайд 34
Суть сортировки:
Сначала сортируются все элементы, отстоящие друг от
друга на три позиции
Затем сортируются элементы, расположенные на
расстоянии двух позиций Наконец, сортируются все соседние элементы
Слайд 35
12
Сортировка Шелла
8
14
6
4
1
2
3
4
1
2
1 шаг. 4 группы из 2-х элементов
1
7
3
4
12
4
8
9
9
1
14
7
6
2
шаг. 2 группы из 4-х элементов
1
2
1
2
1
2
1
2
4
1
6
8
4
Слайд 36
Сортировка Шелла
4
1
6
3 шаг. 1 группа из 8-ми элементов
Массив
отсортирован по возрастанию
по возрастанию
12
14
9
8
7
14
6
4
1
Слайд 37 Пусть нужно отсортировать массив А по возрастанию, в
котором N элементов методом Шелла
Вспомогательные переменные
j – номер первого
элемента остатка.i – номер перемещаемого элемента.
M- оптимальный шаг
P– промежуточное значение, используемое для перемещения элементов массива
Постановка задачи
Слайд 38
Начало алгоритма.
Шаг 1. M=целая часть N/2
Шаг 2. Пока
M0 выполнять
Шаг 2.1. i:=M+1
Шаг 2.2. Пока i
выполнятьШаг 2.2.1. P=A[i]
Шаг 2.2.2. j=i-M
Шаг 2.2.3. Пока j>0 и P
Шаг 2.2.4. A[j+M]=P
Шаг 2.2.5. i=i+1
Шаг 2.3. M=целая часть M/2
Конец алгоритма.
Слайд 39
Начало алгоритма.
Шаг 1. M=целая часть N/2
Шаг 2. Пока
M0 выполнять
Шаг 2.1. i:=M+1
Шаг 2.2. Пока i
выполнятьШаг 2.2.1. P=A[i]
Шаг 2.2.2. j=i-M
Шаг 2.2.3. Пока j>0 и P
Шаг 2.2.4. A[j]=P
Шаг 2.2.5. i=i+1
Шаг 2.3. M=целая часть M/2
Конец алгоритма.
Определение максимальной величины шага
Определение первого и последнего элемента сравнения для текущего шага
Сортировка элементов последовательности
Определение нового шага сравнения
Определение первого и последнего элемента сравнения для текущего шага
Слайд 40
Зачем необходимо это действие?
Начало алгоритма.
Шаг 1. M=целая часть
N/2
Шаг 2. Пока M0 выполнять
Шаг 2.1. i:=M+1
Шаг
2.2. Пока i<=N выполнятьШаг 2.2.1. P=A[i]
Шаг 2.2.2. j=i-M
Шаг 2.2.3. Пока j>0 и P
Шаг 2.2.4. A[j]=P
Шаг 2.2.5. i=i+1
Шаг 2.3. M=целая часть M/2
Конец алгоритма.
Слайд 41
Зачем необходимо это действие?
Начало алгоритма.
Шаг 1. M=целая часть
N/2
Шаг 2. Пока M0 выполнять
Шаг 2.1. i:=M+1
Шаг
2.2. Пока i<=N выполнятьШаг 2.2.1. P=A[i]
Шаг 2.2.2. j=i-M
Шаг 2.2.3. Пока j>0 и P
Шаг 2.2.4. A[j]=P
Шаг 2.2.5. i=i+1
Шаг 2.3. M=целая часть M/2
Конец алгоритма.
Слайд 42
Почему условие выхода из цикла такое?
Начало алгоритма.
Шаг 1.
M=целая часть N/2
Шаг 2. Пока M0 выполнять
Шаг 2.1.
i:=M+1Шаг 2.2. Пока i<=N выполнять
Шаг 2.2.1. P=A[i]
Шаг 2.2.2. j=i-M
Шаг 2.2.3. Пока j>0 и P
Шаг 2.2.4. A[j]=P
Шаг 2.2.5. i=i+1
Шаг 2.3. M=целая часть M/2
Конец алгоритма.
Слайд 44
Придумана Ч.А.Р. Хоаром (Charles Antony Richard Hoare);
В основе
– сортировка обменами;
Основана на делении массива
Слайд 45
Суть сортировки:
Выбирается некоторое значение (x)- барьерный элемент, который
определяется округлением до целого деления количества сортируемых элементов на
2;Просматриваем массив, двигаясь слева направо, пока не найдется элемент, больший x
Затем просматриваем его справа налево, пока не найдется элемент, меньший x
Слайд 46
Суть сортировки:
Меняем найденные элементы местами. В случае, если
не найден наибольший или наименьший элементы, местами меняется средний
элемент с найденным наибольшим или наименьшим элементом;Дойдя до середины имеем 2 части массива;
Процесс продолжается для каждой части, пока массив не будет отсортирован
Слайд 47
Быстрая сортировка
8
12
3
7
19
11
4
16
Барьерный элемент
4
3
7
8
12
3
4
Барьерный элемент
8
12
11
19
Барьерный элемент
12
19
16
19
8>7 переносим в правую
часть, т. к.
16>7 не переносим, 4
местами 4 и 812>7 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим,
7=7 поэтому меняем местами 7 и 12
4>3
Отсортиро-ванная часть
12>11 переносим в правую часть, т. к.
16>11 не переносим, 8<11
поэтому меняем местами 12 и 8
19>11 переносим в правую часть, т. к. 16>11, 12>11,не переносим,
11=11 поэтому меняем местами 11 и 19
Отсортированная часть
19>12 переносим в правую часть, т. к. 16>12,не переносим,
12=12 поэтому меняем местами 12 и 19
19>16
Массив отсортирован по возрастанию
по возрастанию
Слайд 48 Пусть нужно отсортировать массив А по возрастанию, в
котором n элементов быстрым методом
Вспомогательные переменные:
t –конечный элемент
массиваm - начальный элемент массива
x – элемент относительно которого перемещаются все остальные элементы.
w – промежуточное значение, используемое для перемещения элементов массива
Постановка задачи
Слайд 49
Начало алгоритма.
Шаг 1 i=m j=t
Шаг 2 x=A[округление до
целого(m+t)/2]
Шаг 3 Пока i
i:=i+1, иначе
Если A[j]>x то j:=j-1
иначе
w:=A[i]; A[i]:=A[j]; A[j]:=w
i:=i+1, j:=j-1
Шаг 4 Если m
Рекурсивный вызов процедуры
Слайд 50
Начало алгоритма.
Шаг 1 i=m j=t
Шаг 2 x=A[округление до
целого(m+t)/2]
Шаг 3 Пока i
i:=i+1, иначе
Если A[j]>x то j:=j-1
иначе
w:=A[i]; A[i]:=A[j]; A[j]:=w
i:=i+1, j:=j-1
Шаг 4 Если m
Зачем необходимо это действие?
Слайд 51
Начало алгоритма.
Шаг 1 i=m j=t
Шаг 2 x=A[округление до
целого(m+t)/2]
Шаг 3 Пока i
i:=i+1, иначе
Если A[j]>x то j:=j-1
иначе
w:=A[i]; A[i]:=A[j]; A[j]:=w
i:=i+1, j:=j-1
Шаг 4 Если m
Если исключить условие и просто вызвать процедуру, что может произойти?
Слайд 52
Начало алгоритма.
Шаг 1 i=m j=t
Шаг 2 x=A[округление до
целого(m+t)/2]
Шаг 3 Пока i
i:=i+1, иначе
Если A[j]>x то j:=j-1
иначе
w:=A[i]; A[i]:=A[j]; A[j]:=w
i:=i+1, j:=j-1
Шаг 4 Если m
Если изменить условие цикла на i
Слайд 53
Начало алгоритма.
Шаг 1 i=m j=t
Шаг 2 x=A[округление до
целого(m+t)/2]
Шаг 3 Пока i
i:=i+1, иначе
Если A[j]>x то j:=j-1
иначе
w:=A[i]; A[i]:=A[j]; A[j]:=w
i:=i+1, j:=j-1
Шаг 4 Если m
Что происходит в выделенном фрагменте?
Слайд 54
Начало алгоритма.
Шаг 1 i=m j=t
Шаг 2 x=A[округление до
целого(m+t)/2]
Шаг 3 Пока i
i:=i+1, иначе
Если A[j]>x то j:=j-1
иначе
w:=A[i]; A[i]:=A[j]; A[j]:=w
i:=i+1, j:=j-1
Шаг 4 Если m
Что происходит в выделенном фрагменте?
Слайд 55
Начало алгоритма.
Шаг 1 i=m j=t
Шаг 2 x=A[округление до
целого(m+t)/2]
Шаг 3 Пока i
i:=i+1, иначе
Если A[j]>x то j:=j-1
иначе
w:=A[i]; A[i]:=A[j]; A[j]:=w
i:=i+1, j:=j-1
Шаг 4 Если m
Что происходит с равными элементами?
Слайд 57
Параметры оценки алгоритмов
Время сортировки - основной параметр,
характеризующий быстродействие алгоритма
Память – выделяется ли дополнительная
память под временное хранение данных Слайд 58 Устойчивость – отсортированный массив не меняет порядок элементов
с одинаковыми значениями.
Взаимное расположение равных элементов с ключом 1
и дополнительными полями "a", "b", "c"не изменилось
изменилось
Параметры оценки алгоритмов
Слайд 59 Естественность поведения - эффективность метода при обработке
уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя
естественно, если учитывает эту характеристику входной последовательности и работает лучшеПараметры оценки алгоритмов
Слайд 60
Оценка алгоритма сортировки выбором
Общее количество сравнений
C =N-l + N-2 + ...+ 1 = (N2-N)/2
Общее
количество операций
n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = Theta(n2)Число обменов < числа сравнений = время сортировки растет квадратично относительно количества элементов
Слайд 62 Если входная последовательность почти упорядочена, то сравнений будет
столько же
алгоритм ведет
себя неестественно
Слайд 63
Оценка алгоритма сортировки вставкой
Для массива 1 2 3
4 5 6 7 8 потребуется N-1 сравнение.
Для массива
8 7 6 5 4 3 2 1 потребуется (N2-N)/2 сравнение.Общее количество операций Theta(n2)
Слайд 65 Наименьшие оценки эффективности, когда элементы предварительно упорядочены, а
наибольшие – когда элементы расположены в обратном порядке
алгоритм
ведет себя естественно
Слайд 66 Не эффективный метод, так как включение элемента связано
со сдвигом всех предшествующих элементов на одну позицию, а
эта операция неэкономнаВ совокупности устойчивость и естественность поведения алгоритма, делает метод хорошим выбором в соответствующих ситуациях
Слайд 67
Оценка алгоритма сортировки обменом
Количество сравнений
(n2-n)/2
Общее количество операций
Theta(n2)
Слайд 68
Ответьте на следующие вопросы:
Устойчив ли этот метод?
Естественное ли
поведение этого алгоритма?
Слайд 69
Очень медленен и малоэффективен.
На практике, даже с
улучшениями, работает, слишком медленно, поэтому почти не применяется.
Прост, и
его можно улучшать
Слайд 70
Сравнение методов простой сортировки
N – количество элементов,
M
– кол-во пересылок,
C – кол-во сравнений
?
Чему будет равно
количество пересылок
Слайд 71
Выбор метода сортировки
При сортировке маленьких массивов (менее 100
элементов) лучше использовать метод «Всплывающего пузырька»;
Если известно, что список
уже почти отсортирован, то подойдет любой метод;
Слайд 72
Оценка алгоритма Шелла
Время выполнения пропорционально n1.2, т. к.
при каждом проходе используется небольшое число элементов или элементы
массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных
Слайд 73
Оценка алгоритма быстрой сортировки
Если размер массива равен числу,
являющемуся степенью двойки (N=2g), и при каждом разделении элемент
X находится точно в середине массива, тогда при первом просмотре выполняется N сравнений и массив разделится на две части размерами N/2. Для каждой из этих частей N/2 сравнений и т. д. СледовательноC=N+2*(N/2)+4*(N/4)+...+N*(N/N).
Если N не является степенью двойки, то оценка будет иметь тот же порядок
Слайд 74
Общее количество операций Theta(n).
Количество шагов деления (глубина
рекурсии) составляет приблизительно log n, если массив делится на
более-менее равные части. Таким образом, общее быстродействие: O(n log n)Если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности, тогда быстродействие O(n2)
Слайд 75
Метод неустойчив.
Поведение довольно естественно, если учесть, что
при частичной упорядоченности повышаются шансы разделения массива на более
равные частиСортировка использует дополнительную память
Слайд 76
Итоги:
Предпочтительным является метод прямого включения;
Сортировка методом простого обмена
является наихудшей;
Быстрая сортировка превосходит все остальные методы сортировки;
Слайд 77
Контрольные вопросы
Что такое «сортировка»?
В чем заключается метод сортировки
отбором?
В чем заключается метод сортировки вставками?
В чем заключается метод
пузырьковой сортировки?В чем заключается метод быстрой сортировки?
В чем заключается метод сортировки Шелла?
