Алгоритмы сортировки

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Алгоритмы поиска

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

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

В таком случае лучше всего рассматривать процедуру сравнения в виде «черного ящика» – функции с четко определенным интерфейсом, которая в качестве входных параметров принимает указатели на два элемента и возвращает результат сравнения – первый элемент больше, меньше или равен второму.

В последующем изложении все описания алгоритмов даны для работы с классом TList, а функции сравнения имеют следующий тип:

{ Объявление прототипа функции сравнения }

TCompareFunc = function (aData1, aData2: Pointer): Integer;

Тип входных параметров определяет сама функция, и решает, привести ли их к определенному классу или просто к типу, который не является указателем. Пример реализации функции сравнения для целых типа LongWord приведен ниже.

{ Функция сравнения двух целых чисел, заданных своими указателями }

function CompareLongWord(aData1, aData2: Pointer): Integer;

{ Значение первого элемента меньше значения второго }

if LongWord(aData1^) < LongWord(aData2^) then

Result:=-1 else

{ Значения элементов равны }

if LongWord(aData1^) = LongWord(aData2^) then

Result:=0 else

{ Значение первого элемента больше значения второго }

Result:=1;

end;

Линейный поиск. Единственно возможным методом поиска элемента по значению ключа, находящегося в неупорядоченном наборе данных, является последовательный (линейный) просмотр каждого элемента, который продолжается до тех пор, пока не будет найден искомый элемент. Если просмотрен весь набор, но элемент не найден, искомый ключ отсутствует. Для последовательного поиска в среднем требуется (n+1)/2 сравнений и порядок алгоритма линейный O(n).

Программная иллюстрация линейного поиска в неупорядоченном массиве приведена ниже, где aList – исходный массив, aItem – искомый ключ; функция возвращает индекс найденного элемента или -1, если элемент отсутствует.

{ Линейный поиск в неотсортированном массиве }

function LineNonSortedSearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

var i: Integer;

Result:=-1;

for i:=0 to aList.Count-1 do

if aCompare(aList.List[i],aItem) = 0 then

Result:=i;

Break;

end;

end;

Последовательный поиск для отсортированного массива ничем не отличается от приведенного и имеет порядок алгоритма O(n). Однако алгоритм можно несколько улучшить. Если искомого элемента нет в массиве, поиск можно выполнить быстрее, т.к. итерации должны выполняться только до тех пор, пока не будет найден элемент, больший или равный искомому. Все последующие элементы будут больше искомого и поиск можно прекратить.

{ Линейный поиск в отсортированном массиве }

function LineSortedSearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

var i, CompareResult: Integer;

Result:=-1;

{ Искать первый элемент, больший или равный искомому }

for i:=0 to aList.Count-1 do

CompareResult:=aCompare(aList.List[i], aItem);

if CompareResult >= 0 then

if CompareResult = 0 then

Result:=i else

Result:=-1;

Exit;

end;

end;

end;

Обратите внимание, функция сравнения вызывается только один раз при каждой итерации, т.к. временные параметры ее выполнения заранее не известны, и поэтому вызывать ее желательно следует как можно реже.

Бинарный поиск. Другим методом доступа к элементу является бинарный (двоичный или дихотомичный) поиск, который выполняется в заведомо упорядоченной последовательности элементов. Элементы массива должны располагаться в лексикографическом (символьные ключи) или численно (числовые ключи) возрастающем порядке. Для достижения упорядоченности может быть использован один из методов сортировки.

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

Процесс продолжается до тех пор, пока не найден требуемый ключ или не станет пустым интервал, в котором осуществляется поиск. Чтобы найти элемент, в худшем случае требуется log₂(N) сравнений, что значительно лучше, чем при последовательном поиске. Программная иллюстрация бинарного поиска в упорядоченном массиве приведена ниже.

{ Двоичный поиск }

function BinarySearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

var L, R, M, CompareResult: Integer;

{ Значения индексов первого и последнего элементов }

L:=0; R:=aList.Count-1;

while L <= R do

{ Индекс среднего элемента }

M:=(L + R) div 2;

{ Сравнить значение среднего элемента с искомым }

CompareResult:=aCompare(aList.List[M], aItem);

{ Если значение среднего элемента меньше искомого -

переместить левый индекс на позицию до среднего индекса }

if CompareResult < 0 then

L:=M+1 else

{ Если значение среднего элемента больше искомого -

переместить правый индекс на позицию после среднего индекса }

if CompareResult > 0 then

R:=M-1 else

Result:=M;

Exit;

end;

end;

Result:=-1;

end;

Трассировка бинарного поиска ключа 275 в исходной последовательности: {75, 151, 203, 275, 318, 489, 524, 519, 647, 777} представлена в табл. 4.7.

Табл. 4.7. Трассировка бинарного поиска.

Итерация	L	R	M	a[M]

Алгоритм бинарного поиска можно представить несколько иначе, используя рекурсивное описание. В этом случае граничные индексы интервала L и R являются параметрами алгоритма. Рекурсивная процедура бинарного поиска представлена ниже. Для выполнения поиска необходимо при вызове функции задать значения ее формальных параметров L и R – 1 и n соответственно.

{ Рекурсивный алгоритм двоичного поиска }

function BinaryRecurSearch(aList: TList;

aItem: Pointer; L,R: Integer; aCompare: TCompareFunc): Integer;

var i, CompareResult: Integer;

{ Проверка ширины интервала }

if L > R then

Result:=-1 else

i:=(L + R) div 2;

CompareResult:=aCompare(aList.List[i], aItem);

{ Ключ найден, возврат индекса }

if CompareResult = 0 then

Result:=i else

if CompareResult = -1 then

{ Поиск в правом подинтервале }

Result:=BinaryRecurSearch(aList,aItem,i+1,R,aCompare) else

{ Поиск в левом подинтервале }

Result:=BinaryRecurSearch(aList,aItem,L,i-1,aCompare);

end;

end;

Сформулируем задачу сортировки для общего случая следующим образом: имеется некоторое неупорядоченное входное множество ключей и требуется получить выходное множество тех же ключей, упорядоченных по возрастанию или убыванию. Из всех задач программирования сортировка, возможно, имеет самый богатый выбор алгоритмов решения. Назовем некоторые факторы, влияющие на выбор алгоритма (помимо порядка алгоритма).

1. Имеющийся ресурс памяти: должно ли входное и выходное множество располагаться в разных областях памяти или выходное множество может быть сформировано на месте входного. В последнем случае имеющаяся область памяти должна в ходе сортировки динамически перераспределяться между входным и выходным множествами. Для одних алгоритмов это связано с большими затратами, для других – с меньшими.

2. Исходная упорядоченность входного множества: во входном множестве (даже если оно сгенерировано датчиком случайных чисел) могут попадаться уже упорядоченные участки. В предельном случае входное множество может оказаться уже упорядоченным. Одни алгоритмы не учитывают исходной упорядоченности и требуют одного и того же времени для сортировки любого (в том числе уже упорядоченного) множества данного объема, другие выполняются тем быстрее, чем лучше упорядоченность на входе.

3. Временные характеристики операций: при определении порядка алгоритма время выполнения обычно считается пропорциональным числу сравнений ключей. Ясно, что сравнение числовых ключей выполняется быстрее, чем строковых; операции пересылки, характерные для некоторых алгоритмов, выполняются тем быстрее, чем меньше объем записи, и т.п. В зависимости от обрабатываемых данных может быть выбран алгоритм, обеспечивающий минимизацию числа тех или иных операций.

4. Сложность алгоритма: простой алгоритм требует меньшего времени для его реализации и вероятность ошибки меньше. При промышленном изготовлении программного продукта требования соблюдения сроков разработки и надежности могут даже превалировать над требованиями эффективности функционирования.

5. Устойчивость алгоритма: все алгоритмы можно разделить на два типа – устойчивые и неустойчивые. К устойчивой сортировке относятся те алгоритмы, которые при наличии в исходном наборе данных нескольких равных элементов в отсортированном наборе оставляют их в том же порядке, в котором они были изначально. Например, в исходном наборе находятся три элемента с одинаковым значением 42. Пусть элемент A находится в позиции 12, элемент B – в позиции 234, C – 3456. После выполнения устойчивой сортировки они будут находиться в последовательности A,B,C. Неустойчивая сортировка не гарантирует сохранение исходного взаимного порядка, и расположение может быть B,C,A или C,A,B.

Разнообразие алгоритмов сортировки требует некоторой их классификации. Один из известных методов классификация ориентирован на логические характеристики применяемых алгоритмов. Согласно методу любой алгоритм сортировки использует одну из следующих четырех стратегий (или их комбинацию).

1. Стратегия выборки. Из входного множества выбирается следующий по критерию упорядоченности элемент и включается в выходное множество на место, следующее по номеру.

2. Стратегия включения. Из входного множества выбирается следующий по номеру элемент и включается в выходное множество на то место, которое он должен занимать в соответствии с критерием упорядоченности.

3. Стратегия распределения. Входное множество разбивается на ряд подмножеств (возможно, меньшего объема) и сортировка ведется внутри каждого такого подмножества.

4. Стратегия слияния. Выходное множество получается путем слияния небольших упорядоченных подмножеств.

Другим методом классификации является группирования алгоритмов по скорости выполнения. Именно такой метод будет использован при дальнейшем изложении, т.к. он в наибольшей степени отвечает практической применимости тех или иных алгоритмов. Алгоритмы рассмотрены для случая упорядочения по возрастанию ключей. В большинстве примеров в качестве процедуры сортировки будет использоваться следующий прототип:

{ Прототип процедуры сортировки }

TSortProc = procedure (aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Первым параметром следует список, затем границы сортируемой области и функция сравнения.

Дата добавления: 2014-01-07