Содержание
- 2. Алгоритмы сортировки одномерных массивов Под сортировкой понимают процесс перестановки объектов данного массива в определенном порядке. Целью
- 3. Алгоритмы сортировки одномерных массивов Пусть есть последовательность a0, a1... an и функция сравнения, которая на любых
- 4. Алгоритмы сортировки одномерных массивов Если значение функции сравнения зависит только от поля x, то x называют
- 5. Алгоритмы сортировки одномерных массивов Для того, чтобы обоснованно сделать такой выбор, рассмотрим параметры, по которым будет
- 6. Сортировка методом парных перестановок (методом «пузырька») Самый простой вариант алгоритма сортировки массива основан на принципе сравнения
- 7. Сортировка методом парных перестановок (методом «пузырька») Для подсчета количества перестановок целесообразно использовать счетчик – специальную переменную
- 8. Сортировка методом парных перестановок (методом «пузырька») Пример кода программы
- 9. Сортировка методом парных перестановок (методом «пузырька») Результат работы программы Этот алгоритм всегда будет делать шагов, независимо
- 10. Сортировка методом парных перестановок (методом «пузырька») Пузырьковая сортировка имеет такую особенность: неупорядоченные элементы на "большом" конце
- 11. Сортировка модифицированным методом простого выбора Этот метод основывается на алгоритме поиска минимального элемента. В массиве А[1..n]
- 12. Сортировка модифицированным методом простого выбора Рассмотрим алгоритмическое решение задачи на примере сортировки некоторого массива значений по
- 13. Схема метода Через i обозначен счетчик (номер) просмотров элементов массива.
- 14. Схема метода Рассмотрим выполнение сортировки данным методом на конкретном примере. Пусть исходный массив содержит 5 элементов
- 15. Схема метода
- 16. Код программы
- 17. Результат работы программы
- 18. Результат работы программы Как и в пузырьковой сортировке, внешний цикл выполняется n-1 раз, а внутренний –
- 19. Результат работы программы Покажем, почему данная реализация является неустойчивой. Рассмотрим следующий массив из элементов, каждый из
- 20. Результат работы программы Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются
- 21. Сортировка методом простого включения (вставками) В этом методе задача формулируется так: есть часть массива, которая уже
- 22. Сортировка методом простого включения (вставками) Метод выбора очередного элемента из исходного массива произволен, однако обычно (и
- 23. Сортировка методом простого включения (вставками) Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию.
- 24. Сортировка методом простого включения (вставками) Рассмотрим на примере числовой последовательности процесс сортировки методом вставок. Клетка, выделенная
- 25. Код программы
- 26. Результат работы
- 27. Сортировка вставками Это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы); может сортировать массив
- 28. Сортировка вставками Это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы); может сортировать массив
- 29. Быстрая сортировка (quick-sort) Быстрая сортировка является улучшенным вариантом алгоритма сортировки с помощью прямого обмена (пузырьковая сортировка).
- 30. Быстрая сортировка (quick-sort) Общая схема алгоритма: из массива выбирается некоторый опорный элемент a[i] запускается процедура разделения
- 31. Быстрая сортировка (quick-sort) для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него
- 32. Быстрая сортировка (quick-sort) Рассмотрим алгоритм подробнее. На входе массив a[0]...a[N] и опорный элемент p, по которому
- 33. Быстрая сортировка (quick-sort) Рассмотрим работу процедуры для массива a[0]...a[6] и опорного элемента p = a[3]. Теперь
- 34. Быстрая сортировка. Оценка сложности алгоритма Операция разделения массива на две части относительно опорного элемента занимает время
- 35. Быстрая сортировка. Оценка сложности алгоритма Лучший случай. В наиболее сбалансированном варианте при каждой операции разделения массив
- 36. Быстрая сортировка. Оценка сложности алгоритма Худший случай. Реализуется если каждый раз в качестве центрального элемента выбирается
- 37. Быстрая сортировка. Метод неустойчив. Поведение довольно естественно, если учесть, что при частичной упорядоченности повышаются шансы разделения
- 38. Рекурсия В языке Си функции могут вызывать сами себя непосредственно или косвенно, т.е. могут быть рекурсивными.
- 39. Рекурсия Каждая цепочка рекурсивных вызовов должна на каком-то шаге завершиться. Условие полного окончания работы рекурсивной функции
- 40. Рекурсия Применять рекурсивные методы программирования стоит в тех задачах, где рекурсия использована в определении обрабатываемых данных.
- 41. Рекурсия Пример программы вычисляющей факториал числа
- 42. Рекурсия При первом вызове f(5) функция возвращает выражение 5*f(4), т.е. функция f() фактически не возвращает значение,
- 43. Код алгоритма quick-sort
- 45. Скачать презентацию