Использование связанного списка для хранения информации о промежуточных максимумах.

Сортировка посредством выбора.

{сортировка выбором, пример 1}

procedure Selekt (var item: DataArray; count: integer);

Var

i, j, k: integer;

x: DataItem;

Begin

for i: = i to count-1 do

Begin

k: = i;

x: = item[i];

for j: = i+1 to count do { найти элемент с наименьшим значением }

if item[j]< x then

Begin

k: = j;

x: = item[j];

end;

item[k]: = item[i]; { обмен }

item[i]: = x;

end;

end;

Идея метода довольно проста: найти наибольший элемент файла и поставить его на место N, найти следующий максимум и поставить его на место N-1 и т.д. до 2-го элемента. Схема алгоритма имеет следующий вид.

{сортировка выбором, пример 2}

for i: =1 to n-1 do

Begin

k: =i; max: =a[i];

for j: =i+1 to n do

if a[j]> max then

Begin

max: =a[j];

k: =j;

end;

A[k]: =a[i]; a[i]: =max;

end;

Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N*logN, где a, b - неизвестные константы, зависящие от программной реализации алгоритма, log - логарифм по основанию 2.

Использование связанного списка для хранения информации о промежуточных максимумах.

В приведенном выше алгоритме максимум среди K[1]... K[j-1] определяется в цикле от j-1 до 1 c целью обеспечить меньшее число обменов в случае равенства ключей и сохранении прежнего порядка равных элементов. Однако, если изменить порядок просмотра элементов на противоположный и изменить структуру данных, введя дополнительные указатели, можно примерно в два раза сократить число повторений в цикле поиска максимума. Каждый ключ K[i] снабжается указателем L[i] на элемент, максимальный среди первых i-1 элементов так, как показано ниже.

Тогда после обмена элементов K[j] и K[m] поиск максимума в следующем цикле по j можно осуществлять среди элементов K[L[m]]... K[j] при начальных значениях X=K[L[m]], m=L[m], т.к. максимум может " обновиться" только за счет элементов, лежащих правее локального максимума. Таким образом среднее количество просматриваемых при поиске максимума элементов сокращается примерно в два раза. Модифицированный алгоритм имеет следующий вид.

Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N*logN, где a, b - неизвестные константы, зависящие от программной реализации алгоритма, log - логарифм по основанию 2.