Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[0]

Сортировка и поиск: Рецептурный справочник

Томас Ниман

Thomas Niemann

thomasn@ptld.uswest.net

Перевод с английского П.Н.Дубнер infoscope@glasnet.ru

Предисловие

В этой книжечке содержится информация о нескольких алгоритмах сортировки и поиска. Эту информацию можно найти во множестве книг - в большинстве из них предполагается знание математического анализа и теории вероятностей. Хотя формальное исследование алгоритмов и доказательство результатов, описывающих их асимптотические свойства, очень важны, часто важны и возможны чисто интуитивные объяснения.

Здесь все алгоритмы объяснены в наиболее простом виде. Предполагается, что вы владеете Си или Паскалем по крайней мере на начальном уровне. В частности, вы должны знать, что такое массивы и указатели. Материал представлен здесь в порядке от простого к чуть более сложному. Несмотря на то, что этот текст предназначен для начинающих, в нем есть разделы, которые могут оказаться интересными и более продвинутым читателям. В особенности это относится к разделам о хеш-таблицах и скип-списках.

Санта-Круз, КалифорнияТомас Ниман

Март 1995

Замечание переводчика

При чтении RU.ALGORITHMS в русском ФИДО я часто натыкаюсь на малограмотные и/или неверные утверждения. Этот текст показался мне интересным для начинающих - он, по крайней мере, убережет их от совсем уж непростительных заблуждений.

МоскваПавел Дубнер

Февраль 1998


1. Введение

Поиск, вставка и удаление, как известно, - основные операции при работе с данными. Мы начнем с исследования того, как эти операции реализуются над сами известными объектами - массивами и (связанными) списками.

Массивы

На рис.1.1 показан массив из семи элементов с числовыми значениями. Чтобы найти в нем нужное нам число, мы можем использовать линейный поиск - его алгоритм приведен на рис. 1.2. Максимальное число сравнений при таком поиске - 7; оно достигается в случае, когда нужное нам значение находится в элементе А [6]. Если известно, что данные отсортированы, можно применить двоичный поиск (рис. 1.3). Переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M - 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы двое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска - всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Рис. 0.1: Массив

Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Кроме поиска нам необходимо бывает вставлять и удалять элементы. К сожалению, массив плохо приспособлен для выполнения этих операций. Например, чтобы вставить число 18 в массив на рис. 1.1, нам понадобится сдвинуть элементы A[3]...A[6] вниз - лишь после этого мы сможем записать число 18 в элемент А[3]. Аналогичная проблема возникает при удалении элементов. Для повышения эффективности операций вставки/удаления предложены связанные списки.


int function SequentialSearch (Array A , int Lb , int Ub , int Key ); begin

for i = Lb to Ub do

if A (i) = Key then return i ;

return -1; end;

Рис. 0.2: Линейный поиск

int function BinarySearch (Array A , int Lb , int Ub , int Key ); begin do forever

M = (Lb + Ub )/2; if ( Key < AM]) then

Ub = M - 1;

else if (Key > A[MJ) then

Lb = M + 1;

return M ;

if (Lb > Ub ) then

return -1;

Рис. 0.3: Двоичный поиск

Односвязные списки

На рис. 1.4 те же числа, что и раньше, хранятся в виде связанного списка; слово "связанный" часто опускают. Предполагая, что X и P являются указателями, число 18 можно вставить в такой список следующим образом:

X->Next = P->Next; P->Next = X;

Списки позволяют осуществить вставку и удаление очень эффективно. Поинтересуемся, однако, как найти место, куда мы будем вставлять новый элемент, т.е. каким образом присвоить нужное значение указателю P. Увы, для поиска нужной точки придется пройтись по элементам списка. Таким образом, переход к спискам позволяет уменьшить время вставки/удаления элемента за счет увеличения времени поиска.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15]