Алгоритмические модели поиска и сортировки данных
Поиск и сортировка являются классическими задачами теории обработки данных, решают эти задачи с помощью множества различных алгоритмов. Рассмотрим наиболее популярные из них. Для начала введем понятие массива.
Рис. 11.7. Схемы алгоритмов нахождения произведения нечетных чисел
Массивом называют однородный набор величин одного и того же типа, называемых компонентами массива, объединенных одним общим именем (идентификатором) и идентифицируемых (адресуемых) вычисляемыминдексом. Это определение подчеркивает, что все однотипные компоненты массива имеют одно и то же имя, но различаются по индексам, которые могут иметь характер целых чисел из некоторого диапазона, литер, перечисленных констант. Индексы позволяют адресовать компоненты массива, т.е. получить доступ в произвольный момент времени к любой из них как к одиночной переменной (рис. 11.8). Обычный прием работы с массивом - выборочное изменение отдельных его компонент.
Вычисляемые индексы позволяют использовать единое обозначение элементов массива для описания массовых однотипных операций в циклических конструкциях программ. Важной особенностью массива является его статичность. Массив должен быть описан в программе (т.е. определены тип и число компонент) и его характеристики не могут быть изменены в ходе выполнения программы.
Рис. 11.8. Одномерный массив - набор элементов (компонентов)
Компонентами массива могут быть не только простейшие данные, но и структурные, в том числе массивы. В этом случае мы получаем массив массивов - многомерный массив. Для индексации элементарных компонент в этом случае может потребоваться два, три и более индексов.
В некоторых системах программирования существуют специальные виды массивов. Например, массив литер (символов) определяется как строка.
Данные, хранящиеся в массивах, находятся в оперативной памяти компьютера. Это, с одной стороны, ускоряет доступ к ним в ходе решения задачи, а с другой - налагает ограничения на объем возможной информации, организованной в виде массивов. Не следует поэтому, без крайней необходимости, создавать новые массивы для перемещения данных из уже существующих массивов.
Поиск. Для определенности примем, что множество, в котором осуществляется поиск, задано как массив var a:array[0..N] of item, где item - заданный структурированный тип данных обладающий хотя бы одним полем (ключом), по которому необходимо проводить поиск.
Результатом поиска, как правило, служит элемент массива, равный эталону, или отсутствие такового.
Линейный поиск. Процедура заключается в простом последовательном просмотре всех элементов массива и сравнении их с эталоном X.
Алгоритм 1
алг Поиск эталона X в массиве А[1..100]
нач
вывод (“Введите эталон X”)
ввод (x)
нц i
для i=1 до 100
вывод (“Введите ”, i, “ элемент массива А”)
ввод (A[i])
кц i
i:=1
нц пока (i<=100) and (A[i]<>x)
i:=i+1
кц
вывод (x “равен ”,i, “-му элементу массива A”)
кон
Поиск делением пополам. В большинстве случаев процедура поиска применяется к упорядоченным данным (телефонный справочник, библиотечные каталоги и пр.). В подобных ситуациях эффективным алгоритмом является поиск делением пополам. В этом методе сравнение эталона Х осуществляется с элементом, расположенным в середине массива и в зависимости от результата сравнения (больше или меньше) дальнейший поиск проводится в левой или в правой половине массива.
Алгоритм 2
алг Поиск эталона X в массиве А[1..100] делением пополам
нач
вывод (“Введите эталон X”)
ввод (x)
вывод (“Введите размерность массива A”)
ввод (v)
нц i
для i=1 до v
вывод (“Введите ”, i, “ элемент массива А”)
ввод (A[i])
кц i
k:=0
r:=v
нц пока k<r
n:=(k+r) div 2
если A[n]<x то k:=n+1
иначе r:=n
кц
если k>v товывод (“заданного эталона ”,x, “в массиве A нет”)
Иначе
вывод (x “равен ”,n, “-му элементу массива A”)
кон
Например, пусть эталонный ключ х=13, а в массиве имеются следующие элементы: А[1]=1; А[2]=3; А[3]=4; А[4]=7; А[5]=8; А[6]=9; А[7]=13; А[8]=20; А[9]=23. Результатом поиска с применением алгоритма 2 будет значение n = 6.
Задача нахождения максимума (минимума) массива.Найти максимальный элемент массива A[n], где n размерность массива. Алгоритм решения данной задачи приведен на рис. 11.9.
Сортировка массивов. Как и в случае поиска определим массив данных: var a: array [0.. N] of item.
Важным условием сортировки массива большого объема является экономное использование доступной памяти. В прямых методах сортировки осуществляется принцип перестановки элементов «на том же месте». Ниже рассмотрим две группы сортировок: с помощью выбора и обмена.
Сортировка с помощью прямого выбора. Алгоритм прямого выбора является одним из распространенных в силу своей простоты. Сначала определяют минимальный элемент среди всех элементов массива, затем его меняют местами с первым. Далее процесс повторяется с той лишь разницей, что минимальный ищется со второго и меняется со вторым и т.д.
Алгоритм 3
алг Сортировка массива А[1..100] по возрастанию с помощью прямого выбора
нач
вывод (“Введите размерность массива A”)
ввод (n)
нц i
для i=1 до n
вывод (“Введите ”, i, “ элемент массива А”)
ввод (A[i])
кц i
нц i
для i=1 до n-1
min:=A[i]
нц j
для j=i+1 до n
если min>A[j] то
k:=j
min=A[j]
Все
кц j
buffer:=A[i]
A[i]:=min
A[k]:=buffer
кц i
вывод (“Вывод элементов отсортированного массива А”)
нц i
для i=1 до n
вывод (A[i])
кц i
кон
Сортировка с помощью обменов. Характерной чертой алгоритмов сортировки с помощью обмена является обмен местами двух элементов массива после их сравнения друг с другом. В так называемой «пузырьковой сортировке» проводят несколько проходов по массиву, в каждом из которых повторяется одна и та же процедура: сравнение двух последовательно стоящих элементов и их обмен местами в порядке меньшинства (старшинства). Подобная процедура сдвигает наименьшие элементы к левому концу массива. Название этого алгоритма связано с интерпретацией элементов как пузырей в сосуде с водой, обладающих весом соответствующего элемента (при этом массив надо представлять в вертикальном положении). При каждом проходе пузырьки всплывают до своего уровня.
Фрагмент алгоритма пузырьковой сортировки:
нц i
для i=2 до n
нц j
для j=n до i
если A[j-1]>A[j] то
buffer:=A[j-1]
A[j-1]:=A[j]
A[j]:=buffer
Все
кц j
кц i
Например, задан массив чисел A={3, 2, 5, 1}. После первого выполнения первого прохода:
При i=2, имеем: 3215 3125 1325.
При i=3, имеем 1235.
При i=4, имеем 1235.
Пузырьковая сортировка является не самой эффективной, особенно для последовательностей, у которых «всплывающие» элементы находятся в крайней правой стороне. В улучшенной (быстрой) пузырьковой сортировке предлагается производить перестановки на большие расстояния, причем двигаться с двух сторон. Идея алгоритма заключается в сравнении элементов, из которых один берется слева (i = 1), другой - справа (j = n). Если A[i] <= A[j] , то устанавливают j = j - 1 и проводят следующее сравнение. Далее уменьшают j до тех пор, пока A[i] > A[j]. В противном случае меняем их местами и устанавливаем i = i + 1. Увеличение i продолжаем до тех пор, пока не получим A[i] > A[j]. После следующего обмена опять уменьшаем j. Чередуя уменьшение j и увеличение i, продолжаем этот процесс с обоих концов до тех пор, пока не станет i = j. После этого этапа возникает ситуация, когда первый элемент занимает ему предназначенное место, слева от него младшие элементы, а справа - старшие.