Осуществляется поиск искомого элемента массива методами двоичного и линейного поиска
жүктеу/скачать 0,86 Mb.
|
|
Аннотация В курсовом проекте рассматривается нечисленная обработка данных: сортировка и поиск. Выполняется сортировка целочисленных массивов методом подсчетом и вставками. Осуществляется поиск искомого элемента массива методами двоичного и линейного поиска. Подробно описаны способы решения и алгоритмы функций для реализации программы на языке ABC Pascal. 1 Постановка задачи Необходимо разработать программу, реализующую сортировку целочисленного массива. Для чего: Сформировать входной набор данных длиной n=16,128,512,1024 элементов. Разработать алгоритмы линейного, двоичного поиска и алгоритм сортировки методами подсчетом и вставки; Выполнить тестирование программы; Включить в программу счётчики числа операций сравнения и передач управления в операциях поиска и сортировки. Требования к программе: Основные алгоритмы оформить в виде подпрограмм. Результаты работы программ сохранить в текстовом файле; Программа должна быть самодокументированной, то есть содержать комментарии основных параметров и действий. Предусмотреть формирование массива как путем ввода значений с клавиатуры, если размер массива n≤16, так и с использованием датчика случайных чисел. 2 Методы решения задач 2.1 Метод линейного поиска Линейный или последовательный поиск – это простейший метод поиска, который не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Слово «линейный» содержит в себе основную идею данного метода: на некоторой последовательности поочередно просматриваются элементы, каждый из которых сравнивается с искомым. Если они совпадают, то поиск заканчивается. В лучшем случае предстоит произвести всего одно сравнение, а в худшем n, где n — количество элементов в списке. В неупорядоченном массиве лучше всего применить линейный поиск, который состоит в сравнении каждого элемента массива с искомым ключевым словом. При таком поиске в среднем необходимо просмотреть половину массива для нахождения нужного элемента. Введем условную единицу времени, равную времени, затраченному на сравнение двух элементов. Следовательно, среднее время поиска элемента в массиве равно , где N – количество элементов в массиве. Применение линейного поиска целесообразна для массивов небольшого размера, но для массива, содержащего большое количество элементов, она может оказаться слишком медленной. Рассмотрим линейный поиск на примере массива из 16 элементов. Пусть дан неупорядоченный массив А: 16 22 55 21 35 62 20 77 45 35 97 15 78 1 7 99 и необходимо найти элемент k со значением 15 (таблица 1). Для решения этой задачи создается цикл с параметром (for i:=1 to n) с помощью которого каждый элемент массива последовательно (A[i]) сравнивается с искомым числом (k): A[1]=16, 16≠15 => A[2]=22, 22≠15 => A[3]=55, 55≠15 => A[4]=21, 21≠15 => A[5]=35, 35≠15 => A[6]=62, 62≠15 => A[7]=20, 20≠15 => A[8]=77, 77≠15 => A[9]=45, 45≠15 => A[10]=35, 35≠15 => A[11]=97, 97≠15 => A[12]=15, 15=15 => ключ найден, поиск завершен. Таблица 1 - Линейный поиск
Из таблицы 1 видно, что для нахождения элемента k=55 пришлось выполнить 12 сравнений. Если бы элемента 55 не оказалось под номером 12, то поиск выполнялся бы до его нахождения, либо до окончания массива 2.2 Метод двоичного поиска Двоичный или бинарный поиск – это поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Принцип двоичного поиск основан на том, что поиск начинается с середины массива, затем сравниваем ключевое число с элементом, находящимся в середине таблицы. Ключевое число может быть равно, больше или меньше проверяемой величины. Он работает путем сравнения искомого ключа k со средним элементом массива А[m]. Если ключ и элемент массива равны, то элемент найден. Поиск завершается. Если больше, взять верхнюю половину данного массива в качестве новой таблицы для поиска. Если меньше, использовать нижнюю половину массива К ↨ А[0]…A[m-1] A[m] A[m+1]…A[n-1] Поиск в этой части, Поиск в этой части, если K Этот метод фактически делит массив пополам при каждой проверке, систематически локализуя искомую величину. Поиск является безуспешным, если длина последнего массива для поиска уменьшается до 1, а искомая величина не найдена. Поиск заканчивается при совпадении искомого элемента с элементом, который является границей между частями множества или при отсутствии искомого элемента. Введем условную единицу времени, равную времени, затраченному на сравнение двух элементов. Следовательно, среднее время поиска элемента в массиве равно Tср = [время проверки] × log2N, где N – количество элементов в массиве. Рассмотрим двоичный поиск на тех же (упорядоченных) элементах, что и в линейном поиске: 1 7 15 16 20 21 22 35 35 45 55 62 77 78 97 99 Необходимо найти элемент k=15 Элемент был найден на шаге 3: Перед началом поиска устанавливаем левую и правую границы массива: left = 0, right = 15
Шаг 1. Ищем индекс середины массива (округляем в меньшую сторону): mid = (15+0)/2=8 Сравниваем значение по этому индексу с искомым: 35 > 15 Шаг 1
Сдвигаем правую границу: right = mid = 8 Шаг 2. Ищем индекс середины массива (округляем в меньшую сторону): mid = (8+0)/2=4 Сравниваем значение по этому индексу с искомым: 20 > 15 Шаг 2 Шаг 1
Сдвигаем правую границу: right = mid = 4 Шаг 3. Ищем индекс середины массива (округляем в меньшую сторону): mid = (4+0)/2=2 Сравниваем значение по этому индексу с искомым: 15 = 15 Шаг 3 Шаг 2 Шаг 1
Таким образом, решение найдено. Чтобы уменьшить количество шагов поиска можно сразу смещать границы поиска на элемент, следующий за серединой отрезка: left = mid + 1 right = mid — 1
Рисунок 1 – Иллюстрация двоичного поиска. 2.3 Метод сортировки вставками Сортировка вставками – алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. При сортировке вставками на каждом шаге i, 1 ≤ i ≤ n, ключ ki последовательно сравнивается с уже размещенными по возрастанию ключами k1 , k2 ,…, ki-1 до тех пор, пока не найдется минимальный интервал, концами которого являются уже упорядоченные ключи kj и kj’. Затем ключ ki помещается между ключами kj и kj’ и на соответствующее место устанавливается элемент Ri. После прохождения всех ключей получается упорядоченный список. При этом из необходимости выполнения попарной проверки ключей следует, что алгоритм требует О (n2) операций. Общая суть сортировок вставками: 1. Перебираются элементы в неотсортированной части массива. 2. Каждый элемент вставляется в отсортированную часть массива на то место, где он должен находиться. Сортируемый массив можно разделить на две части — отсортированная часть и неотсортированная. В начале сортировки первый элемент массива считается отсортированным, все остальные — не отсортированные. Начиная со второго элемента массива и заканчивая последним, алгоритм вставляет неотсортированный элемент массива в нужную позицию в отсортированной части массива. Таким образом, за один шаг сортировки отсортированная часть массива увеличивается на один элемент, а неотсортированная часть массива уменьшается на один элемент. Выполнение алгоритма сортировка вставками основано на внедрении в отсортированную часть массива элемента, следующего за этой частью, если он удовлетворяет условию сортировки. На первом шаге сортировки второй элемент сравнивается с первым, на втором шаге третий элемент сравнивается с двумя первыми и так далее. Среди уже отсортированных i-1 элементов массива вставляют i-й элемент без нарушения порядка, то есть при вставке i-го элемента на j-е место (j 16 22 55 21 35 62 20 77 45 35 97 15 78 1 7 99 Шаг 1. На первом шаге сравниваются два начальных ключа. Второй ключ больше первого, поэтому он остается на месте. 16 22 55 21 35 62 20 77 45 35 97 15 78 1 7 99 Шаг 2. На втором шаге из неупорядоченной последовательности выбирается ключ и сравнивается с двумя упорядоченными ранее ключами. Поскольку он больше предыдущих, этот ключ остается на месте. 16 22 55 21 35 62 20 77 45 35 97 15 78 1 7 99 Шаг 3. На третьем шаге выбирается ключ и сравнивается с тремя упорядоченными ранее ключами. Ключ 21, больший ключа 16, затем сравнивается с ключом 22 и 55, и выясняется, что ключ 21 меньше. Поскольку ключ 21 меньше ключей 22 и 55, он перемещается перед ключами 22 и 55. Затем ключи 22 и 55 сдвигаются вправо на одну позицию. 16 22 55 21 35 62 20 77 45 35 97 15 78 1 7 99 16 21 22 55 35 62 20 77 45 35 97 15 78 1 7 99 Шаг 4. На четвертом шаге выбирается ключ и сравнивается с предыдущими упорядоченными ключами. Ключ 35, больший ключи 16, 21, 22 сравнивается затем с ключом 55, и выясняется, что ключ 35 меньше, и ключ 35 перемещается перед ключом 55. 16 21 22 55 35 62 20 77 45 35 97 15 78 1 7 99 16 21 22 35 55 62 20 77 45 35 97 15 78 1 7 99 Шаг 5. На пятом шаге выбирается ключ и сравнивается с предыдущими упорядоченными ключами. Ключ 62 больше предыдущих и остается на месте. 16 21 22 35 55 62← 20 77 45 35 97 15 78 1 7 99 16 21 22 35 55 62 20 77 45 35 97 15 78 1 7 99 Шаг 6. На шестом шаге выбирается ключ и сравнивается с предыдущими упорядоченными ключами. Ключ 20, больший ключа 16, сравнивается затем с ключами 21, 22, 35, 55, 62 и выясняется, что ключ 20 меньше, поэтому ключ 20, перемещается перед ключами 22, 35, 55, 62, и эти ключи сдвигаются вправо на одну позицию. 16 21 22 35 55 62 20 77 45 35 97 15 78 1 7 99 16 20 21 22 35 55 62 77 45 35 97 15 78 1 7 99 Шаг 7. На седьмом шаге выбирается ключ 77 и сравнивается с предыдущими упорядоченными ключами. Поскольку он больше предыдущих, остается на месте. 16 20 21 22 35 55 62 77← 45 35 97 15 78 1 7 99 16 20 21 22 35 55 62 77 45 35 97 15 78 1 7 99 Шаг 8.
На восьмом шаге выбирается ключ и сравнивается с предыдущими упорядоченными ключами. Ключ 45, больший ключа 16, 20, 21, 22, 35, сравнивается затем с ключами 55, 62, 77 и выясняется, что ключ 45 меньше ключей 55, 62, 77 и сдвигаются вправо на одну позицию. 16 20 21 22 35 55 62 77 45 35 97 15 78 1 7 99 16 20 21 22 35 45 55 62 77 35 97 15 78 1 7 99 Шаг 9. На девятом шаге выбирается ключ и сравнивается с предыдущими упорядоченными ключами. Ключ 35, больший ключи 16, 20, 21, 22, сравнивается затем с ключом 45, 55, 62, 77 и выясняется, что ключ 35 меньше. Поскольку ключи 45, 55, 62, 77 сдвигаются вправо на одну позицию. 16 20 21 22 35 45 55 62 77 35 97 15 78 1 7 99 16 20 21 22 35 35 45 55 62 77 97 15 78 1 7 99 Шаг 10. На десятом шаге выбирается ключ 97 и сравнивается с предыдущими упорядоченными ключами. Поскольку он больше предыдущих, остается на месте. 16 20 21 22 35 35 45 55 62 77 97 ← 15 78 1 7 99 16 20 21 22 35 35 45 55 62 77 97 15 78 1 7 99 Шаг 11. На одиннадцатом шаге выбирается ключ 15 и сравнивается с предыдущими упорядоченными ключами. Поскольку он меньше всех предыдущих, ключ перемещается на место первого элемента, поэтому каждый ключ сдвигается вправо на одну позицию. 16 20 21 22 35 35 45 55 62 77 97 15 78 1 7 99 15 16 20 21 22 35 35 45 55 62 77 97 78 1 7 99 Шаг 12. На двенадцатом шаге выбирается ключ 78 и сравнивается с предыдущими упорядоченными ключами. Поскольку он меньше 97, перемещается на место 97, который сдвигается вправо на одну позицию. 15 16 20 21 22 35 35 45 55 62 77 97 78 1 7 99 15 16 20 21 22 35 35 45 55 62 77 78 97 1 7 99 Шаг 13. На тринадцатом шаге выбирается ключ 1 и сравнивается с предыдущими упорядоченными ключами. Поскольку он меньше всех предыдущих, перемещается на место первого элемента 15, который сдвигаются остальные ключи вправо на одну позицию. 15 16 20 21 22 35 35 45 55 62 77 78 97 1 7 99 1 15 16 20 21 22 35 35 45 55 62 77 78 97 7 99 Шаг 14. На четырнадцатом шаге выбирается ключ 7 и сравнивается с предыдущими упорядоченными ключами. Он меньше всех предыдущих, кроме единицы, и перемещается перед элементом 15. Затем сдвигаются остальные ключи вправо на одну позицию. 1 15 16 20 21 22 35 35 45 55 62 77 78 97 7 99 1 7 15 16 20 21 22 35 35 45 55 62 77 78 97 99 Шаг 15. На пятнадцатом шаге выбирается ключ 99 и сравнивается с предыдущими упорядоченными ключами. Он больше всех предыдущих, поэтому ключ остается без изменения. 1 7 15 16 20 21 22 35 35 45 55 62 77 78 97 99← 1 7 15 16 20 21 22 35 35 45 55 62 77 78 97 99 В результате получается упорядоченный список. 1 15 16 20 21 22 35 35 45 55 62 77 97 78 7 99 2.4 Параллельная сортировка Бэтчера. Параллельная сортировка Бэтчера. Чтобы получить алгоритм обменной сортировки, время работы которого имеет порядок, меньший N2 необходимо подобрать для сравнений пары несоседних ключей (Кi, Кj); иначе придется выполнить столько операций обмена записей, сколько инверсий имеется в исходной перестановке. Среднее число инверсий равно ( N2-N). В 1964 году К. Э. Бэтчер открыл интересный способ программирования последовательности сравнений, предназначенной для поиска возможных обменов. Его метод далеко не очевиден. В самом деле, обосновать его справедливость весьма сложно, поскольку выполняется относительно мало сравнений. Схема сортировки Бэтчера несколько напоминает сортировку Шелла, но сравнения выполняются по-новому, а потому цепочки операций обмена записей не возникает. В качестве примера сравним табл. 1 и 5.2.1-3. Сортировка Бэтчера действует, как 8-, 4-, 2- и 1-сортировка, но сравнения не перекрываются. Поскольку в алгоритме Бэтчера, по существу, происходит слияние пар рассортированных подпоследовательностей, его можно назвать обменной сортировкой со слиянием. Алгоритм М. (Обменная сортировка со слиянием). Записи R1,...,RN перекомпоновываются в пределах того же пространства в памяти. После завершения сортировки их ключи будут упорядочены: K1≤…≤KN. Предполагается, что N 2 M1. [Начальная установка р.] Установить р ←2t-1, где t = [lg N] — наименьшее целое число, такое, что 2t≥ N. (Шаги М2-М5 будут выполняться с р=2t-1, 2t-2,…,1) M2. [Начальная установка q,r,d] Установить q2t-1, r0, dр. M3. [Цикл по i] Для всех I, таких, что 0≤i Так, 13˄21 = (1101)2˄(10101)2 = (00101)2 = 5. К этому моменту d -нечетное кратное p(т. е. частное от деления d на p нечетно), а p - степень двойки, так что i˄p≠(i+d)˄p Отсюда следует, что шаг М4 можно выполнять при всех нужных значениях i в любом порядке или даже одновременно.) M4. [Сравнение/обмен Ri+1:Ri+d+1.] Если Ki+1 >Ki+d+1, поменять местами записи Ri+1Ri+d+1 М5. [Цикл по q.] Если q≠p, установить dq-p, qq/2, rp и возвратиться к шагу M3. M6. [Цикл по p) (К этому моменту перестановка K1,K2…KN будет p-упорядочена.) Установить p[p/2]. Если p> 0, возвратиться к шагу М2. | В табл. 1 этот метод проиллюстрирован при N= 16. Обратите внимание на то, что, по существу, алгоритм сортирует N элементов путем независимой сортировки подмассивов R1,R3,R5,… и R2,R4,R6 после чего выполняются шаги M2-М5 при р = 1 для слияния двух рассортированных последовательностей. Чтобы доказать, что магическая последовательность сравнений и/или обменов, описанная в алгоритме М, действительно позволяет рассортировать любую последовательность R1,R2,…RN необходимо показать только, что в результате выполнения шагов М2-М5 при p=1 будет слита любая 2-упорядоченная последовательность R1,R2,…RN. Каждая 2-упорядоченная перестановка множества {1, 2,…,N} соответствует на решетке единственному пути из вершины (0,0) к ([N/2], [N/2]). На рис. 18, (а) показан пример при № = 16, соответствующий перестановке 1 3 2 4 10 5 11 6 13 7 14 8 15 9 16 12. При р=1, q=2t-1,r=0,d=1 шаге МЗ выполняется сравнение (и, возможно, обмен) записей R1:R2:R3 и т.д. Этой операции соответствует простое преобразование пути на решетке: “перегиб” относительно диагонали при необходимости, чтобы путь нигде не проходил выше диагонали. На следующей итерации шага МЗ имеем р=r=1 и d=2t-1-1, 2t-2-1, …,1. В результате произойдет сравнение и/или обмен записей R2:R2+d; R4:R4+d и т.д. Опять же, имеется простая геометрическая интерпретация: путь “перегибается” относительно прямой, расположенной на (d+1) единиц ниже диагонали (рис. 18, (с) и (d)). В конце концов, получаем путь, изображенный на рис. 18, (е), который соответствует полностью рассортированной перестановке. На этом “геометрическое доказательство” справедливости алгоритма Бэтчера завершается (данный алгоритм можно было бы назвать сортировкой посредством перегибов!) MIX- программа для алгоритма М приведена в упр. 12. К сожалению, количество вспомогательных операций, необходимых для управления последовательностью сравнений, весьма велико, так что программа менее эффективна, чем другие рассмотренные выше методы. Однако она обладает одним важным компенсирующим качеством: все сравнения и/или обмены, определяемые данной итерацией шага МЗ, можно выполнять одновременно на компьютерах или в сетях, которые реализуют параллельные вычисления. С такими параллельными операциями сортировка осуществляется за $ [18 №] (8 №] + 1) шагов, и это один из самых быстрых общих методов среди всех известных. Например, 1 024 элемента можно рассортировать методом Бэтчера всего за 55 параллельных шагов. Его ближайшим соперником является метод Пратта, который затрачивает 40 или 73 шага в зависимости от того, как считать: если допускать перекрытие сравнений до тех пор, пока не потребуется выполнять перекрывающиеся обмены, то для сортировки 1 024 элементов методом Пратта требуется всего 40 циклов сравнения и/или обмена. жүктеу/скачать 0,86 Mb. Достарыңызбен бөлісу:
|