Алгоритмы сортировки Лектор: к.т.н., доцент кафедры вычислительной техники Токарева Ольга Сергеевна Алгоритмы и технология их разработки

Постановка задачи сортировки Пусть надо упорядочить N элементов (записей) R 1, R 2, R 3,…, R N. Каждая запись R j имеет ключ K j, который управляет процессом сортировки. Отношение порядка < на множестве ключей(линейное упорядочение): 1. Справедливо только одно соотношение (закон трихотомии): a b. 2. Если a

Сортировка представляет собой процесс упорядочивания элементов в массиве по возрастанию или убыванию. Внутренняя сортировка – сортировка данных, полностью помещающихся в оперативной памяти. Внешняя сортировка – cортировка данных с ленты или диска, т.е. их внешней памяти. Обращение к оперативной памяти требует меньше времени, поэтому внутренние сортировки эффективнее. Сортировка называется устойчивой, если при ее применении положение записей с равными ключами (или элементов массива с одинаковыми значениями) не изменяется. Существует большое количество алгоритмов сортировки, базирующихся на трех основных методах (алгоритмах): - обменом; - выбором; - вставкой.

Критерии оценки алгоритма сортировки Критериями для сравнительной оценки качества алгоритма сортировки являются объем используемой памяти и время работы программы. Хорошей по критерию памяти считается такая сортировка, при которой сортировка происходит в том же массиве, где находились исходные данные, т.е. внутренняя сортировка. При оценке времени сортировки используются два показателя: число сравнений ключей (С) и число пересылок данных (M). Теоретическая сложность алгоритма O(N) – величина порядка N. Хорошими считаются сортировки, у которых число сравнений СN*Ln(N), где N – число элементов массива (O(N*Ln(N)). К простым относятся такие сортировки, для которых СN 2 (O(N 2 )). Показатели C и M существенно зависят от первоначальной упорядоченности массива. Наиболее затратный случай – когда элементы массива упорядочены в обратном порядке.

Пусть алгоритм последовательно выполняет сравнения: A[i] > A[i+1]. При каждом сравнении возможны два исхода: 1)A[i] > A[i+1], результат сравнения истинен, в этом случае элементы массива A[i] и A[i+1] должны обменяться своими значениями; 2) A[i]

j:=1 Начало Ввод n, A(n) i:=1 Конец Вывод A(n) i:=i+1 i

Улучшение пузырьковой сортировки Вход: массив A, состоящий из элементов A[1], A[2],..., A[n-1], A[n] t := истина цикл пока t: t := ложь цикл для j = 1, 2,..., n 1: если A[j] > A[j+1], то: обменять местами элементы A[j] и A[j+1] t := истина Если на очередной итерации цикла по t перестановок не было – заканчиваем работу

Пример Первый проход: ( ) ( ) - сравниваются два первых элемента, 6>2, меняются местами ( ) ( ), меняются местами, т.к. 6 > 5 ( ) ( ), меняются местами, т.к. 6 > 3 ( ) ( ), не меняются местами, т.к. 9 > 6 Второй проход: ( ) ( ) ( ), меняются местами, так как 5 > 3 ( ) Третий проход: ( ) ( ) ( ) перестановок не было, заканчиваем работу

Улучшение пузырьковой сортировки Шейкерная сортировка: Проходим массив слева направо – максимальный элемент встает на свое место, затем проходим массив справа налево – минимальный встает на свое место и т.д.

Сортировка методом выбора i:=k+1 Начало Ввод n, A(n) Nmin:=k к:=1 B:=A[Nmin] A[Nmin]:= A[k] A[k]:=B Конец Вывод A(n) k:=k+1 k

Сортировка методом вставки B0 A[j+1]:=A[j] Начало Ввод A(n) B:=A[i] j:=i-1 A[j+1]:=B i:=2 Конец Вывод A(n) i:=i+1 i

Сортировка слиянием Принцип «Разделяй и властвуй» - разбиение задачи размерности n на подзадачи размерности m 1, m 2,…,m n, такие что m1+m2+…+mn

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

Поиск элемента с заданным значением

Постановка задачи: Дан упорядоченный целочисленный массив A, содержащий n элементов (A(n)), и некоторое числовое значение p. Требуется найти такой номер i элемента массива, для которого A[i] = p, или определить, что такого номера нет. Задача может быть решена просмотром элементов массива в цикле до первого совпадения значения элемента A[i] с p. Поскольку после нахождения искомого значения просматривать массив дальше нецелесообразно, в алгоритме следует использовать цикл while. Этот цикл завершится, когда будет достигнут конец массива или найдено искомое значение. Если при этом окажется, что параметр цикла стал больше, чем длина массива, то искомого значения в массиве нет. В противном случае элемент со значением p находится в позиции i.

Поиск элемента с заданным значением Поиск можно значительно ускорить, если использовать свойство упорядоченности массива. Идея быстрого алгоритма поиска состоит в том, что в массиве выделяется область «подозрительных» элементов, т.е. таких, что если искомый элемент в массиве существует, он обязательно будет внутри этой области. Каждое сравнение выполняется так, чтобы область сокращалась вдвое, поэтому алгоритм получил название дихотомического (деление пополам). Для этого на каждом шаге цикла производится сравнение p с элементом A[c], расположенным в середине «подозрительной» области. При этом возможны два случая: 1) A[c] < p, тогда из области «подозрительных» элементов отбрасываются все, начиная с начала области до номера c включительно; 2) A[c] >= p, тогда из области «подозрительных» элементов отбрасываются все, начиная с номера c + 1 до конца области.

Метод поиска с возвратом A BC D E F J K L MN

Метод разработки алгоритмов «сверху-вниз» Наиболее важным методом разработки алгоритмов является метод пошаговой детализации или метод разработки «сверху-вниз». Первоначально продумывается и фиксируется множество данных и результатов алгоритмов без детальной проработки отдельных частей. Далее задачу разбивают на автономные части, каждая из которых существенно проще. Может оказаться необходимым повторить процесс детализации многократно. Это определяется сложностью решаемых задач. Конечным уровнем детализации алгоритма можно считать такой, при котором в алгоритме нет действий более крупных, чем: обращение к готовому алгоритму; вычисление арифметического выражения и присваивание значения переменной; сравнение арифметических выражений или переменных; ввод или вывод данных; и т.п.

Главным требованием к алгоритму является его работоспособность – способность функционировать в заданных режимах и объемах обрабатываемой информации в соответствии с программным документом при отсутствии сбоев технических средств. Создавая алгоритм, необходимо помнить о дальнейшей работе над ним, об отладке программы, которая будет создана на основе этого алгоритма, а также о пользователях, которым потребуется этот алгоритм. Поэтому одним из важнейших требований к алгоритму является его простота и понятность. Исходя из этих требований, особенно удобным представляется использование основных алгоритмических структур, описанных выше. Их важной особенностью является то, что они имеют один вход и один выход и могут соединяться друг с другом в любой последовательности. Это дает наглядную и простую структуру алгоритма, по которой далее легко составить программу. Метод разработки алгоритмов «сверху-вниз»

Обычно в программах процесс идет сверху вниз, что позволяет анализировать алгоритм как обычный текст. Если технологию разработки алгоритмов «сверху-вниз» объединить с использование только структурных схем, то получиться новая технология, которая называется структурным программированием сверху вниз. Разработанные в соответствие с ней алгоритмы обладают в некотором смысле свойством правильности. В таких алгоритмах, как правило, меньше ошибок, хотя в целом эта технология не гарантирует от неточностей, связанных с невнимательностью. В структурированных алгоритмах и программах легче разобраться. Метод разработки алгоритмов «сверху-вниз»