Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

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

Оказывается, можно. Посмотрите внимательно на реализацию бинарного поиска для массива, приведенную в листинге 4.9. Когда выполнение цикла завершается, и искомый элемент не найден, что можно определить на основании значений переменных L, R и M? Во-первых, очевидно, что L>R. Рассмотрим, что происходит при выполнении цикла в последний раз. В начале цикла мы должны были иметь L=R или L=R-1. При этом вычисление даст, что M=L. Если бы разница между L и R была больше, скажем, L=R-2, тогда значение M попало бы в диапазон между L и R, и цикл был бы выполнен, по крайней мере, еще один раз.

Если при выполнении цикла в последний раз искомый элемент был меньше, чем элемент в позиции M, то переменная R получила бы значение M-1, и цикл завершился бы. Мы уже знаем, что искомого значения не было до элемента M, поэтому можно сделать вывод, что новый элемент должен быть вставлен между элементами M-1 и M. Другими словами, мы вставляем элемент в позицию M.

С другой стороны, если бы искомый элемент был больше элемента в позиции M, то переменная L получила бы значение M+1. В этом случае можно принять, что в начале цикла L=R. В противном случае цикл был бы выполнен еще один раз. Мы уже знаем, что искомого значения не было после элемента M, поэтому можно сделать вывод, что новый элемент должен быть вставлен между элементами M и M+1. Другими словами, мы вставляем элемент в позицию M+1.

Таким образом, новый элемент должен вставляться в позицию M или M+1 в зависимости от того, что произошло при последнем выполнении цикла. Но давайте подумаем еще раз. Разве между описанными двумя случаями нет ничего общего? Оказывается, что на место вставки в обоих случаях указывает значение переменной L. Таким образом, вставка выполняется в позицию L.

В приведенном ниже листинге показано, каким образом можно вставить новый элемент в массив TList. В коде предполагается, что если вновь вставляемый элемент уже присутствует в массиве, вставка будет игнорироваться (другими словами, повторение элементов не допускается). Функция возвращает индекс вставленного элемента. Легко проверить, что приведенная функция будет работать даже в случае, когда список перед вставкой пуст.

Листинг 4.11. Вставка элемента в отсортированный массив TList с помощью алгоритма бинарного поиска

function TDTListSortedInsert(aList : TList; aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

L, R, M : integer;

CompareResult : integer;

begin

{задать значения левого и правого индексов}

L := 0;

R := pred(aList.Count);

while (L <= R) do begin

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

M := (L + R) div 2;

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

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

{если значение среднего элемента меньше заданного значения, переместить левый индекс на позицию после среднего элемента}

if (CompareResult < 0) then

L := succ(M)

{если значение среднего элемента больше заданного значения, переместить правый индекс на позицию перед средним элементом}

else if (CompareResult > 0) then

R := pred(M)

{в противном случае элемент найден, выйти из функции}

else begin

Result := M;

Exit;

end;

end;

Result := L;

aList.Insert(L, aItem);

end;

Для связного списка функция будет еще проще, поскольку нам не нужно решать, каким образом вычислять индекс для вставки нового элемента. Поиск сам указывает на точку вставки элемента.

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

Сортировка при повседневном программировании встречается очень часто. Когда на форме выводится поле со списком, его удобнее и легче использовать, если элементы в списке отсортированы в алфавитном порядке. Мы, как люди, при изучении данных предпочитаем просматривать их в определенном порядке, который помогает визуально отображать распределение данных. Представьте себе, как сложно было бы пользоваться телефонной книгой, если бы она была отсортирована не по фамилиям в алфавитном порядке, а в каком-нибудь другом порядке. Главы в этой книге, как и в любой другой, расположены в соответствие с их номерами. Что касается разработки, то с программами удобнее работать, если данные отсортированы. Например, алгоритм двоичного поиска быстрее алгоритма последовательного поиска при большом количестве элементов в контейнере, поэтому чтобы выиграть в скорости поиска, имеет смысл поддерживать отсортированный порядок элементов.

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

Алгоритмы сортировки являются одним из наиболее изученных направлений теории вычислительных систем. В общем случае определить характеристики выполнения сортировки достаточно просто. Можно доказать, что любой алгоритм сортировки, основанный на сравнении, принадлежит к классу O(n log(n)). Ниже мы рассмотрим несколько таких алгоритмов.

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

Коды для основных алгоритмов сортировки, описанных в этой главе, можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSorts.pas.

Перед тем, как приступить к подробному рассмотрению алгоритмов, давайте введем несколько фундаментальных правил. Все типы сортировок, которые будут описаны ниже, используют сравнение. Чтобы алгоритм "знал", как располагать элементы в списке, их необходимо сравнивать между собой. Мы не будем приводить примеры сортировки для целых чисел, строк или переменных типа TMyRecord. Давайте рассматривать проблему сортировки более широко. Примем, что необходимо выполнить сортировку элементов, которые заданы указателями. Это тот же принцип, который мы использовали при изучении структур данных: данные задаются их указателями. Отделяя данные от манипулирования ими, мы уделяем больше внимания характеристикам алгоритмов или структур данных, а не занимаемся ненужной разработкой или оптимизацией методов для целых чисел, строк или других типов данных.