Алгоритмы сортировки и поиска

Июль 23, 2022

Главная
Информатика
Алгоритмы сортировки и поиска

Содержание

2. { Алгоритмы сортировки } Задача сортировки. Пусть есть множество из N элементов R1, R2,… RN. Каждый
3. { Случайная сортировка } Алгоритм: перемешать последовательность случайным образом; проверить выполнено ли условие сортировки. Возможно, самый
4. { Сортировка выбором } Алгоритм: найти наименьший элемент в неотсортированной части массива; поставить его в начало;
5. { Сортировка вставками } Алгоритм: из неотсортированной части берется элемент; вставляется в отсортированную часть на своё
6. { Сортировка “Методом Пузырька” } Алгоритм: последовательно сравниваются пары элементов идущих друг за другом; в случае
7. { Сортировка “Методом Пузырька” } Алгоритм: последовательно сравниваются пары элементов идущих друг за другом; в случае
8. { Сортировка слиянием } Алгоритм: Сортируемый массив разбивается на две части примерно одинакового размера; Каждая из
9. { Сортировка слиянием } Алгоритм: Сортируемый массив разбивается на две части примерно одинакового размера; Каждая из
10. { Сортировка слиянием } Алгоритм: Сортируемый массив разбивается на две части примерно одинакового размера; Каждая из
11. { Сортировка слиянием }
12. { Быстрая сортировка } Является улучшенным вариантом алгоритма сортировки с помощью прямого обмена («Пузырьковая сортировка»), весьма
13. { Быстрая сортировка } def quick_sort(a, l, r): if (r > l): v, i, j =
14. { Нахождение медианы } k-й порядковой статистикой массива называется k-й по величине элемент массива: максимальный (минимальный)
15. { Алгоритмы поиска } Задача поиска. Пусть есть множество из N элементов R1, R2,… RN. Каждый
16. { Последовательный поиск } Рассмотрим алгоритм поиска с помощью последовательного сравнения.
17. { Алгоритмы поиска } Методы сужения области – аналогии с поиском корня. Корни нелинейного уравнения. Пусть
18. { Алгоритмы поиска } Методы сужения области – аналогии с поиском корня. Двухточечные методы (уменьшение отрезка
20. Скачать презентацию

Слайд 2

{ Алгоритмы сортировки }
Задача сортировки.
Пусть есть множество из N элементов R1,

R2,… RN. Каждый элемент характеризуется некоторой информацией и ключом K1. На множестве ключей определены операции сравнения: «>», «<» и т.д.
Задачей сортировки является нахождение такой перестановки ключей p1, p2,… pN, после которой ключи расположились бы в заданном порядке:
неубывания
невозрастания
Для классификации алгоритмов сортировки используются:
сложность;
потребности в дополнительной памяти;
области хранения данных (внутренняя (в ОЗУ) и внешняя сортировка (вне ОЗУ));
свойство устойчивые (меняется ли положение элементов с одинаковыми ключами);
наличие в алгоритме операции сравнения.

Слайд 3

{ Случайная сортировка }
Алгоритм:
перемешать последовательность случайным образом;
проверить выполнено ли условие сортировки.
Возможно,

самый неэффективный алгоритм.
Сложность: O(n*n!).
(Колода в 32 карты будет сортироваться компьютером в среднем 2,7⋅1019 лет.)

Слайд 4

{ Сортировка выбором }
Алгоритм:
найти наименьший элемент в неотсортированной части массива;
поставить его

в начало;
сдвинуть начало неотсортированной части.
Сложность: O(n2).

Слайд 5

{ Сортировка вставками }
Алгоритм:
из неотсортированной части берется элемент;
вставляется в отсортированную часть

на своё мосто (в начале массива).
Сложность: O(n2).

Слайд 6

{ Сортировка “Методом Пузырька” }
Алгоритм:
последовательно сравниваются пары элементов идущих друг за

другом;
в случае несоответствия выбранному порядку меняются местами.
Сложность: O(n2).

Слайд 7

{ Сортировка “Методом Пузырька” }
Алгоритм:
последовательно сравниваются пары элементов идущих друг за

другом;
в случае несоответствия выбранному порядку меняются местами.
Сложность: O(n2).

Слайд 8

{ Сортировка слиянием }
Алгоритм:
Сортируемый массив разбивается на две части примерно одинакового

размера;
Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
Два упорядоченных массива половинного размера соединяются в один.
Сложность: O(n log2 n).

Слайд 9

{ Сортировка слиянием }
Алгоритм:
Сортируемый массив разбивается на две части примерно одинакового

Слайд 10

{ Сортировка слиянием }
Алгоритм:
Сортируемый массив разбивается на две части примерно одинакового

Слайд 11

{ Сортировка слиянием }

Слайд 12

{ Быстрая сортировка }
Является улучшенным вариантом алгоритма сортировки с помощью прямого

обмена («Пузырьковая сортировка»), весьма низкой эффективности. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы.
Таким образом, улучшение неэффективного прямого метода сортировки дало один из наиболее эффективных методов.
Алгоритм:
выбрать (опорным) элемент из массива;
перераспределить элементы в массиве так, что элементы меньше опорного помещаются перед ним, а больше или равные после;
применить первые два шага к подмассивам слева и справа от опорных элементов, пока в подмассивах не останется не более одного элемента.
Сложность: Средняя O(n log2 n), Худшая O(n2).

Худший случай.
Если каждое разделение даёт два подмассива размерами 1 и n-1, т.е. при каждом разбиении больший массив будет укорачиваться на 1. Это может произойти, если за опорный будет выбраться либо наименьший, либо наибольший элемент из всех обрабатываемых.
При выборе опорного элемента — первого или последнего в массиве, — такой эффект даст уже отсортированный массив.

Слайд 13

${ Быстрая сортировка } def quick_sort(a, l, r): if (r >$

{ Быстрая сортировка }
def quick_sort(a, l, r):
if (r > l):
v,

i, j = a[r], l - 1, r
while (True):
i, j = i + 1, j - 1
while(a[i] < v): i = i + 1
while(a[j] > v): j = j - 1
if (i >= j): break
a[i], a[j] = a[j], a[i]
a[i], a[r] = a[r], a[i]
quicksort(a, l, i - 1)
quicksort(a, i + 1, r)

Слайд 14

{ Нахождение медианы }
k-й порядковой статистикой массива называется k-й по величине

элемент массива:
максимальный (минимальный) элемент массива: 1-ая (N-ая) порядковая статистика;
медиана – «средний» по величине элемент, примерно половина элементов не больше, примерно половина элементов не больше, примерно половина – не меньше.
Алгоритм нахождения k-й порядковой статистики методом «разделяй и властвуй»:
выберем случайным образом элемент v массива S;
разобьём массив на три: Sl, элементы которого меньше, чем v; Sv, элементы которого равны v, и Sr, элементы которого больше, чем v;
введём функцию Selection(S, k), где S — массив, а k — номер порядковой статистики:

Слайд 15

{ Алгоритмы поиска }
Задача поиска.
Пусть есть множество из N элементов R1,

R2,… RN. Каждый элемент характеризуется некоторой информацией и ключом Ki. На множестве ключей определены операции сравнения: «>», «<» и т.д.
Задачей поиска является нахождение индекса ключа, совпадающего со значением key.
Алгоритмы поиска:
линейный, последовательный поиск (неотсортированный массив);
поиск сужением зоны (отсортированный массив).
Выбором структуры данных (устройством хранимой информации) можно расставить приоритеты:
быстрое и простое изменение данных;
Быстрый поиск.

Слайд 16

{ Последовательный поиск }
Рассмотрим алгоритм поиска с помощью последовательного сравнения.

Слайд 17

{ Алгоритмы поиска }
Методы сужения области – аналогии с поиском корня.
Корни

нелинейного уравнения.
Пусть дана некоторая функция f(x) и требуется найти значения x, для которых
Определение. Значение x*, при котором f(x*) = 0, называется корнем (или решением) уравнения.
Геометрически корень уравнения есть точка пересечения графика функции y = f(x) с осью абсцисс.
На графике изображены три корня:
При этом они отличаются
Корни типа называются простыми, а . – кратными (непростыми).
Большинство методов решения уравнений ориентировано на отыскание простых корней.

Слайд 18

{ Алгоритмы поиска }
Методы сужения области – аналогии с поиском корня.
Двухточечные

методы (уменьшение отрезка локализации).
Методы выбора точки с:
Метод половинного деления (метод дихотомии)
Метод золотого сечения
Метод хорд

Алгоритмы сортировки и поиска

Содержание

{ Алгоритмы сортировки }Задача сортировки.Пусть есть множество из N элементов R1,

{ Случайная сортировка }Алгоритм:перемешать последовательность случайным образом;проверить выполнено ли условие сортировки.Возможно,

{ Сортировка выбором }Алгоритм:найти наименьший элемент в неотсортированной части массива;поставить его

{ Сортировка вставками }Алгоритм:из неотсортированной части берется элемент;вставляется в отсортированную часть

{ Сортировка “Методом Пузырька” }Алгоритм:последовательно сравниваются пары элементов идущих друг за

{ Сортировка “Методом Пузырька” }Алгоритм:последовательно сравниваются пары элементов идущих друг за

{ Сортировка слиянием }Алгоритм:Сортируемый массив разбивается на две части примерно одинакового

{ Сортировка слиянием }Алгоритм:Сортируемый массив разбивается на две части примерно одинакового

{ Сортировка слиянием }Алгоритм:Сортируемый массив разбивается на две части примерно одинакового

{ Сортировка слиянием }

{ Быстрая сортировка }Является улучшенным вариантом алгоритма сортировки с помощью прямого

{ Быстрая сортировка }def quick_sort(a, l, r): if (r > l): v,

{ Нахождение медианы }k-й порядковой статистикой массива называется k-й по величине

{ Алгоритмы поиска }Задача поиска.Пусть есть множество из N элементов R1,

{ Последовательный поиск }Рассмотрим алгоритм поиска с помощью последовательного сравнения.

{ Алгоритмы поиска }Методы сужения области – аналогии с поиском корня.Корни

{ Алгоритмы поиска }Методы сужения области – аналогии с поиском корня.Двухточечные

Похожие презентации

{ Алгоритмы сортировки }
Задача сортировки.
Пусть есть множество из N элементов R1,

{ Случайная сортировка }
Алгоритм:
перемешать последовательность случайным образом;
проверить выполнено ли условие сортировки.
Возможно,

{ Сортировка выбором }
Алгоритм:
найти наименьший элемент в неотсортированной части массива;
поставить его

{ Сортировка вставками }
Алгоритм:
из неотсортированной части берется элемент;
вставляется в отсортированную часть

{ Сортировка “Методом Пузырька” }
Алгоритм:
последовательно сравниваются пары элементов идущих друг за

{ Сортировка “Методом Пузырька” }
Алгоритм:
последовательно сравниваются пары элементов идущих друг за

{ Сортировка слиянием }
Алгоритм:
Сортируемый массив разбивается на две части примерно одинакового

{ Сортировка слиянием }
Алгоритм:
Сортируемый массив разбивается на две части примерно одинакового

{ Сортировка слиянием }
Алгоритм:
Сортируемый массив разбивается на две части примерно одинакового

{ Быстрая сортировка }
Является улучшенным вариантом алгоритма сортировки с помощью прямого

{ Быстрая сортировка }
def quick_sort(a, l, r):
if (r > l):
v,

{ Нахождение медианы }
k-й порядковой статистикой массива называется k-й по величине

{ Алгоритмы поиска }
Задача поиска.
Пусть есть множество из N элементов R1,

{ Последовательный поиск }
Рассмотрим алгоритм поиска с помощью последовательного сравнения.

{ Алгоритмы поиска }
Методы сужения области – аналогии с поиском корня.
Корни

{ Алгоритмы поиска }
Методы сужения области – аналогии с поиском корня.
Двухточечные