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