Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
12. Алгоритмы поиска и сортировки информации. Оценка временной сложности. Варианты усовершенствования алгоритмов сортировки.
Одной из основных задач информатики как науки является накопление информации. Для быстрого поиска информации необходимо специальное программно-алгоритмическое обеспечение. Основой являются 2 программы: программа сортировки непрерывно поступающей информации (по ключевым словам, по авторам и т.д.) и программа поиска информации. От эффективности и скорости работы программ зависит время получения информации. Алгоритмы и программы сортировки и поиска непрерывно совершенствуются, что вызвано необходимостью создания быстродействующих информационно-поисковых систем, способных справиться с непрерывно нарастающим объемом информации.
Сортировка – процесс упорядочивания заданного множества элементов по заданному признаку. Алгоритмы сортировки отличаются друг от друга степенью эффективности – количество сравнений и количество обменов, произведенных в процессе сортировки.
Можно сортировать:
- по возрастанию
- по не убыванию (следующий элемент не меньше предыдущего)
- по убыванию
- по не возрастанию
1. Сортировка простым выбором.
На каждом шаге сортировки из последовательности выбирается минимальный элемент и переносится в конец выходной последовательности. Найдем в таблице элемент с наименьшим значением и поменяем его местами с первым элементом. После этого те же действия проделаем с оставшимися (без первого) N-1 элементами таблицы, затем с N-2 элементами и т. д., пока не останется один элемент - последний. Он будет наибольшим. Эффективность, количество операций сравнения: С=n(n-1)/2=O(n2)
n – число элементов массива (входных данных).
2. Сортировка простым обменом («метод пузырька»)
Практически не требует рабочих ячеек, но работает медленно. Может служить идеальным методом сортировки в условиях, когда память ПЭВМ ограничена, а время исполнения не очень существенно. Для выполнения обмена требуется дополнительная переменная, сохраняющая на время обмена одно из значений.
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде.
Чтобы оценить скорость, определим число сравнений значений. На первом проходе сравнивается (N-1) пара значений, на втором (N-2) пары; на каждом следующем проходе число сравнений убывает на 1, пока не станет равным 1. Общее число операций сравнения: C=1+2+3+...+(n-2)+(n-1)=(n-1)*(n-1+1)/2=n*(n-1)/2=n2/2 =O(n2)
3. Сортировка простыми вставками.
На каждом шаге алгоритма выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
Количество сравнений, эффективность: C=о(n) – в лучшем случае, в худшем C=o(n2)
4. Сортировка подсчета.
Идея алгоритма заключается в простом подсчете количества вхождений каждого числа в массив. Это делается так: выполним один проход массива и для каждого числа из отрезка [0, max] подсчитаем сколько раз оно встретится. Вычисленные количества сохраним в специальном массиве счетчиков. Затем запишем в массив - результат (а это может быть и исходный массив) каждое число столько раз, чему равно значение соответствующего ему счетчика, то есть, сколько раз оно встретилось.
Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти (массив состоит из n чисел в диапазоне от 0 до k-1)
Поиск информации
Поиск заключается в отыскании элемента (в массиве), значение которого совпадает с ключом поиска. Пример - отыскание элемента данных, включающего фамилию и адрес, по заданной фамилии.
I. Линейный поиск
1. Цикл с параметром. Для того чтобы не было лишних проверок вводим цикл с параметром (while, repeat). Как только мы находим первое вхождение элемента в массив – программа завершается.
2. Использование «барьерного элемента». В этом случае используется массив с количеством элементов N+1, где на N+1 место записывается элемент X, который и будет барьерным элементом (Х – искомый элемент). Число сравнении зависит от места элемента, который нужно найти, в худшем случае – N+1, в среднем – (N+1)/div 2. Эффективность: С=O(N)
II. Бинарный поиск (метод деления пополам, дихотомия) — классический алгоритм поиска элемента в отсортированном массиве.
Элемент сравнивается со средним (по номеру) элементом массива, если он равен среднему элементу, то задача решена. Если больше среднего, то это значит, что искомый элемент расположен ниже среднего элемента. Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента. После того как определена часть массива, в которой может находиться искомый элемент, вычисляется новое среднее и поиск продолжается.
Количество сравнений в таком алгоритме: C=O(n*logn)
III. Поиск подстроки в строке.
1. Метод предельного поиска. Даны две строки, нужно ответить на вопрос: является ли строка Х подстрокой строки S, причем нужно найти только первое вхождение. Ищем позицию, на которой началось совпадение первого символа, далее продолжаем сравнение подстроки со строкой.