Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Листинг 5.6. Сортировка методом выбора
procedure TDSelectionSort(aList : TList;
aFirst : integer; aLast : integer;
aCompare : TtdCompareFunc);
var
i, j : integer;
IndexOfMin : integer;
Temp : pointer;
begin
TDValidateListRange(aList, aFirst, aLast, 'TDSelectionSort');
for i := aFirst to pred(aLast) do
begin
IndexOfMin := i;
for j := succ(i) to aLast do
if (aCompare(aList.List^[j], aList.List^[IndexOfMin]) < 0) then
IndexOfMin := j;
if (aIndexOfMin <> i) then begin
Temp := aList.List^[i];
aList.List^[i] := aList.List^[IndexOfMin];
aList.List^[IndexOfMin] := Teilend;
end;
end;
Рисунок 5.3
Как видите, в приведенном коде снова присутствуют два вложенных цикла, следовательно, сортировка методом выбора относится к алгоритмам класса O(n(^2^)). В первом цикле индекс проходит значения от aFast до aLast-1 и при каждом его выполнении во внутреннем цикле определяется элемент с минимальным значением в оставшейся части списка. В отличие от нашего примера с картами, внутренний цикл заранее не знает, каковым будет минимальный элемент в списке, поэтому ему нужно просмотреть все элементы. После обнаружения минимального элемента он переставляется в требуемую позицию.
Сортировка методом выбора интересна одной своей особенностью. Количество выполняемых сравнений для первого прохода равно n, для второго - n-1 и т.д. Общее количество сравнений будет равно n (n + 1)/2 = 1, т.е. сортировка принадлежит к классу алгоритмов O(n(^2^)). Тем не менее, количество перестановок намного меньше: при каждом выполнении внешнего цикла производится всего одна перестановка. Таким образом, общее количество перестановок (n - 1), т.е. O(n). Что это означает на практике? Если стоимость перестановки элементов намного больше, чем время сравнения (под стоимостью в данном случае понимается время или требуемые ресурсы), сортировка методом выбора оказывается достаточно эффективной.
Сортировка методом выбора относится к группе устойчивых алгоритмов. Поиск наименьшего значения будет возвращать первое в списке наименьшее значение из нескольких имеющихся. Таким образом, равные значения будут находиться в отсортированном списке в том же порядке, в котором они были в исходном списке.
Сортировка методом вставок
И последний алгоритм из первого рассматриваемого нами набора - сортировка методом вставок, или сортировка простыми вставками (Insertion sort). Этот алгоритм покажется знакомым всем, кто играет в такие карточные игры, как вист или бридж, поскольку большинство игроков сортирует свои карты именно так.
Рисунок 5.4. Стандартная сортировка методом вставок
Начинаем с левого края колоды. Сравниваем две первые карты и располагаем их в правильном порядке. Смотрим на третью карту. Вставляем ее в требуемое место по отношению к первым двум картам. Смотрим на четвертую карту и вставляем ее в требуемое место по отношению к первым трем картам. Те же операции выполняем с пятой, шестой, седьмой и всеми последующими картами. При перемещении слева направо левая часть колоды будет отсортированной.
Листинг 5.7. Стандартная сортировка методом вставок
procedure TDInsertionSortStd(aList : TList;
aFirst : integer;
aLast : integer;
aCompare : TtdCompareFunc);
var
i, j : integer;
Temp : pointer;
begin
TDValidateListRange(aList, aFirst, aLast, 'TDInsertionSortStd');
for i := succ(aFirst) to aLast do
begin
Temp := aList.List^[i];
j :=i;
while (j > aFirst) and (aCompare(Temp, aList.List^[j-1]) < 0) do
begin
aList.List^[j] := aList.List^[j-1];
dec(j);
end;
aList.List^[j] := Temp;
end;
end;
В
Давайте посмотрим на внутренний цикл. Его выполнение завершается при соблюдении одного из двух условий: достигнуто начало списка, т.е. текущее значение меньше значений всех уже отсортированных элементов, или обнаружено значение, меньшее текущего. Тем не менее, обратите внимание, что первое условие проверяется при каждом выполнении внутреннего цикла, несмотря на то что оно соблюдается достаточно редко, когда текущее значение меньше, чем значения всех уже отсортированных элементов, однако оно предотвращает выход за пределы списка. Традиционным методом исключения этой дополнительной проверки является введение в начало списка сигнального элемента, который меньше любого другого элемента в списке. К сожалению, в общем случае минимальный элемент в списке заранее неизвестен и, кроме того, в списке нет места для вставки дополнительного элемента. (Теоретически потребуется скопировать весь список в другой, размер которого больше на один элемент, установить значение первого элемента в этом новом списке равным минимальному значению из сортируемого списка, а затем после сортировки скопировать элементы в исходный список. И все это ради того, чтобы исключить одну проверку. Нет уж, спасибо.)
Рисунок 5.5. Сортировка методом вставок
Существует более эффективный метод оптимизации: просмотреть весь список, найти элемент с наименьшим значением и переставить его на первое место (фактически это выполнение первого цикла Сортировки методом выбора). Теперь, когда первый элемент находится в требуемой позиции, можно выполнять стандартную процедуру метода вставок и игнорировать возможность выхода за начало списка.
Листинг 5.8. Оптимизированная сортировка методом вставок
procedure TDInsertionSort(aList : TList;
aFirst : integer;
aLast : integer;
aCompare : TtdCompareFunc);
var
i, j : integer;
IndexOfMin : integer;
Temp : pointer;
begin
TDValidateListRange(aList, aFirst, aLast, 'TDInsertionSort');
{найти наименьший элемент и поместить его в первую позицию}
IndexOfMin := aFirst;
for i := succ(aFirst) to aLast do
if (aCompare(aList.List^[i], aList.List^[IndexOfMin]) < 0) then