Презентация «Сортировка массивов»

Смотреть слайды в полном размере
Презентация «Сортировка массивов»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 44 слайда и доступен в формате ppt. Размер файла: 574.98 KB

Просмотреть и скачать

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


Скачать презентацию

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