Содержание
- 2. Сортировка объектов – расположение объектов по возрастанию или убыванию согласно определенному линейному отношению порядка
- 3. Сортировка объектов: Внутренняя Внешняя
- 4. Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке.
- 6. Алгоритм сортировки вставкой
- 7. Суть сортировки: Упорядочиваются два элемента массива Вставка третьего элемента в соответствующее место по отношению к первым
- 8. Сортировка вставкой 13 6 2 10 8 13 6 8 2 13 6 8 8 13
- 9. Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом вставки Вспомогательные переменные j
- 10. Начало алгоритма. Шаг 1 j:=2, Шаг 2 Пока j Шаг 2.1 i:=j; f:=0, Шаг 2.2 Пока
- 11. Начало алгоритма. Шаг 1 j:=2, Шаг 2 Пока j Шаг 2.1 i:=j; f:=0, Шаг 2.2 Пока
- 12. Начало алгоритма. Шаг 1 j:=2, Шаг 2 Пока j Шаг 2.1 i:=j; f:=0, Шаг 2.2 Пока
- 13. Начало алгоритма. Шаг 1 j:=2, Шаг 2 Пока j Шаг 2.1 i:=j; f:=0, Шаг 2.2 Пока
- 14. Начало алгоритма. Шаг 1 j:=2, Шаг 2 Пока j Шаг 2.1 i:=j; f:=0, Шаг 2.2 Пока
- 15. Начало алгоритма. Шаг 1 j:=2, Шаг 2 Пока j Шаг 2.1 i:=j; f:=0, Шаг 2.2 Пока
- 16. Начало алгоритма. Шаг 1 j:=2, Шаг 2 Пока j Шаг 2.1 i:=j; f:=0, Шаг 2.2 Пока
- 17. Алгоритм сортировки выбором
- 18. Суть сортировки: Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем
- 19. 13 6 2 10 8 Сортировка выбором Min 2 Min 6 Min 8 13 Min 10
- 20. Постановка задачи Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом выбора. Вспомогательные
- 21. Начало алгоритма. Шаг 1 j:=1, Шаг 2 Пока j Шаг 2.1 min:=a[j], Imin:=j, i:=j+1 Шаг 2.2
- 22. Начало алгоритма. Шаг 1 j:=1, Шаг 2 Пока j Шаг 2.1 min:=a[j], Imin:=j, i:=j+1 Шаг 2.2
- 23. Начало алгоритма. Шаг 1 j:=1, Шаг 2 Пока j Шаг 2.1 min:=a[j], Imin:=j, i:=j+1 Шаг 2.2
- 24. Алгоритм сортировки обменом («пузырьковая»)
- 25. Суть сортировки: Последовательно просматривается массив и сравнивается каждая пара элементов между собой. При этом "неправильное" расположение
- 26. Сортировка обменом 13 6 2 10 8 Первый просмотр 6 13 8 13 13 2 10
- 27. Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом обмена Вспомогательные переменные j
- 28. Начало алгоритма. Шаг 1 j:=N, Шаг 2 Пока j>=2 выполнять: Шаг 2.1 i:=1; , Шаг 2.2
- 29. Начало алгоритма. Шаг 1 j:=N, Шаг 2 Пока j>=2 выполнять: Шаг 2.1 i:=1; , Шаг 2.2
- 30. Начало алгоритма. Шаг 1 j:=N, Шаг 2 Пока j>=2 выполнять: Шаг 2.1 i:=1; , Шаг 2.2
- 31. Алгоритм сортировки Шелла
- 32. Классифицируется как «слияние вставкой»; Называется «сортировкой с убывающим шагом» Общий метод, который использует сортировку вставкой, применяет
- 33. Условия реализации: Конкретная последовательность шагов может быть другой, но последний шаг должен быть равен 1; Следует
- 34. Суть сортировки: Сначала сортируются все элементы, отстоящие друг от друга на три позиции Затем сортируются элементы,
- 35. 12 Сортировка Шелла 8 14 6 4 1 2 3 4 1 2 1 шаг. 4
- 36. Сортировка Шелла 4 1 6 3 шаг. 1 группа из 8-ми элементов Массив отсортирован по возрастанию
- 37. Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом Шелла Вспомогательные переменные j
- 38. Начало алгоритма. Шаг 1. M=целая часть N/2 Шаг 2. Пока M 0 выполнять Шаг 2.1. i:=M+1
- 39. Начало алгоритма. Шаг 1. M=целая часть N/2 Шаг 2. Пока M 0 выполнять Шаг 2.1. i:=M+1
- 40. Зачем необходимо это действие? Начало алгоритма. Шаг 1. M=целая часть N/2 Шаг 2. Пока M 0
- 41. Зачем необходимо это действие? Начало алгоритма. Шаг 1. M=целая часть N/2 Шаг 2. Пока M 0
- 42. Почему условие выхода из цикла такое? Начало алгоритма. Шаг 1. M=целая часть N/2 Шаг 2. Пока
- 43. Алгоритм быстрой сортировки
- 44. Придумана Ч.А.Р. Хоаром (Charles Antony Richard Hoare); В основе – сортировка обменами; Основана на делении массива
- 45. Суть сортировки: Выбирается некоторое значение (x)- барьерный элемент, который определяется округлением до целого деления количества сортируемых
- 46. Суть сортировки: Меняем найденные элементы местами. В случае, если не найден наибольший или наименьший элементы, местами
- 47. Быстрая сортировка 8 12 3 7 19 11 4 16 Барьерный элемент 4 3 7 8
- 48. Пусть нужно отсортировать массив А по возрастанию, в котором n элементов быстрым методом Вспомогательные переменные: t
- 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. Оценка алгоритма сортировки выбором Общее количество сравнений C =N-l + N-2 + ...+ 1 = (N2-N)/2
- 61. Устойчив ли этот метод? Не устойчив
- 62. Если входная последовательность почти упорядочена, то сравнений будет столько же алгоритм ведет себя неестественно
- 63. Оценка алгоритма сортировки вставкой Для массива 1 2 3 4 5 6 7 8 потребуется N-1
- 64. Устойчив ли этот метод? Устойчив порядок элементов с одинаковыми ключами не изменяется
- 65. Наименьшие оценки эффективности, когда элементы предварительно упорядочены, а наибольшие – когда элементы расположены в обратном порядке
- 66. Не эффективный метод, так как включение элемента связано со сдвигом всех предшествующих элементов на одну позицию,
- 67. Оценка алгоритма сортировки обменом Количество сравнений (n2-n)/2 Общее количество операций Theta(n2)
- 68. Ответьте на следующие вопросы: Устойчив ли этот метод? Естественное ли поведение этого алгоритма?
- 69. Очень медленен и малоэффективен. На практике, даже с улучшениями, работает, слишком медленно, поэтому почти не применяется.
- 70. Сравнение методов простой сортировки N – количество элементов, M – кол-во пересылок, C – кол-во сравнений
- 71. Выбор метода сортировки При сортировке маленьких массивов (менее 100 элементов) лучше использовать метод «Всплывающего пузырька»; Если
- 72. Оценка алгоритма Шелла Время выполнения пропорционально n1.2, т. к. при каждом проходе используется небольшое число элементов
- 73. Оценка алгоритма быстрой сортировки Если размер массива равен числу, являющемуся степенью двойки (N=2g), и при каждом
- 74. Общее количество операций Theta(n). Количество шагов деления (глубина рекурсии) составляет приблизительно log n, если массив делится
- 75. Метод неустойчив. Поведение довольно естественно, если учесть, что при частичной упорядоченности повышаются шансы разделения массива на
- 76. Итоги: Предпочтительным является метод прямого включения; Сортировка методом простого обмена является наихудшей; Быстрая сортировка превосходит все
- 77. Контрольные вопросы Что такое «сортировка»? В чем заключается метод сортировки отбором? В чем заключается метод сортировки
- 79. Скачать презентацию