Поиск и сортировка в языке Паскаль

Размещено на http://www.allbest.ru/

Министерство образования и науки Украины

Национальный технический университет Украины «КПИ»

Факультет Информатики и вычислительной техники

Курсовая робота:

ПОИСК И СОРТИРОВКА В ЯЗЫКЕ ПАСКАЛЬ

Киев

2011

1. Поиск

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

Не следует смешивать понятие поиска с операцией прямого доступа к компоненте, которая для регулярных структур обеспечивается селектором.

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

Время поиска оценивается достаточно просто. Если предположить, что структура данных содержит n компонент, то среднее время поиска можно принять равным n/2*t, где t - время, затрачиваемое на один шаг просмотра. Действительно, компонента с искомым значением может быть в лучшем случае найдена на первом шаге и в худшем на последнем; n шагов понадобится и для того, чтобы убедиться в отсутствии такой компоненты в структуре.

Одним из основных методов эффективного поиска является метод дихотомии, иначе двоичного (бинарного) или логарифмического поиска. Метод применим к упорядоченным по некоторому признаку данным. Понятие “упорядочивание” можно пояснить на примере последовательности с элементами a1, a2 , ... , an . Если такая последовательность задана, то упорядочивание означает перестановку этих элементов в порядке aк1, aк2, ..., ak, при котором заданной функции упорядочивания f соответствует отношение f(ak1 ) f(ak2 ) , ... , f (akn ).

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

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

Считать первым индексом последовательности l, последним - r. Положить l=1, r=n. Перейти к пункту 2.

Положить k=m div 2. Перейти к пункту 3.

Если значение элемента ak равно искомому, то поиск прекратить, иначе перейти к пункту 4.

Если значение ak меньше искомого, то положить r=k-1 , иначе положить l=k+1. Перейти к пункту 2.

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

Приведенная оценка худшего случая не совсем точна. В действительности методу свойственна некоторая асимметрия. Анализируя метод следует учитывать, что при делении интервала поиска пополам действительное число сравнений для n элементов может быть на 1 больше ожидаемого из-за округления для нечетных n. В результате поиск элемента в “нижней” части осуществляется в среднем несколько быстрее, чем в “верхней” части, однако, для грубой оценки асимметрией можно пренебречь.

Ниже метод дихотомии иллюстрируется примером программы поиска элемента с заданным значением в векторе w, компоненты которого имеют тип Integer, т. е. принадлежат к порядковому типу и, поэтому, соответствуют понятию ключа. Вектор читается из корневого каталога диска A.

program Prim5_3;

uses Crt;

type

Index=1..4096;

Vector=array[Index] of Integer;

var

N,Svar : Integer;

I,L,R : Index;

Name : string;

W : Vector;

F : file of Integer;

begin

ClrScr;

Write ('Введите путь и имя файла ');

Read (Name);

Write ('Введите значение искомой компоненты ');

Read (SVar);

Assign (F, `A:\+Name');

Reset (F);

N :=FileSize(F);

if N > 4096

then

Write ('Ошибка в исходных данных')

else

begin

for I :=1 to N do {цикл формирования вектора}

Read(F,W[I]);

L :=1;

R :=N;

while (W[I]<>SVar) and (L<=R) do

begin

I :=(L+R) div 2;

if SVar < W[I]

then

R :=I - 1

else

L :=I+1

end;

if W[I]=SVar

then

WriteLn('Искомое значение находится в ',i,'-й компоненте')

else

WriteLn('В векторе нет искомой компоненты')

end;

close (F);

ReadKey

end. {Prim5_3}

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

2. Сортировка

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

Как уже отмечалось, функция упорядочения не вычисляется по какому-то специальному правилу, а ее значение содержится в каждом элементе в виде явной компоненты (поля) и называется ключом. Следовательно, в общем случае, для представления элемента ai желательно использовать структуру данных типа record. Описание типа с именем Item (элемент), который будет использоваться в последующих алгоритмах сортировки выглядит следующим образом:

type

Item=record

Key : Integer;

{описание других компонент}

end;

"Другие компоненты" - это все существенные данные об элементе, а поле Key служит для идентификации элементов. При рассмотрении алгоритмов сортировки ключ является единственной существенной компонентой. В определении остальных полей нет необходимости, поскольку они однозначно связаны с ключом структурой record. Выбор ключа типа Integer произволен. В качестве ключа можно использовать любой тип данных, на котором задано отношение порядка.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не изменяется при сортировке. Устойчивость сортировки необходима в тех случаях, когда элементы упорядочены (рассортированы) по каким-то вторичным ключам, т.е. по свойствам, не отраженным в первичном ключе.

Основное требование к сортировке массивов - экономичное использование памяти. Это означает, что переупорядочение элементов нужно выполнять in situ (на том же месте). Методы, которые пересылают элементы из одного массива в другой, ниже не рассматриваются.

С учетом критерия экономии памяти, классификацию методов (алгоритмов) сортировки можно выполнить в соответствии с их эффективностью, т.е. экономией времени или быстродействием. Оценка эффективности основывается на подсчете числа необходимых сравнений ключей (С) и пересылок элементов (Р). Эти числа определяются как функции от числа n сортируемых элементов. При этом следует помнить, что пересылка, как правило, требует больше времени, чем сравнение. Хорошие алгоритмы сортировки требуют порядка n*log(n) операций, простые - n2. Хотя сложные методы требуют меньшего числа операций, эти операции в свою очередь более сложны, поэтому существенный выигрыш от их применения может быть получен при достаточно больших (порядка нескольких сотен) значениях n. При малых значениях n простые методы работают быстрее.

Целью последующего обзора методов сортировки является иллюстрация применения метода последовательных уточнений к формулировке алгоритмов решения определенного класса задач. Аналитические выражения для оценки их временной cложности, используемые ниже при сравнении методов и алгоритмов, заимствованы в [14] и носят весьма приближенный характер. Последнее обусловлено случайным характером априорной упорядоченности исходного массива (последовательности) перед сортировкой. В этом случае приходится усреднять так называемые граничные оценки для лучшего и худшего из вариантов. Кроме того, строгое доказательство некоторых положений, связанных с анализом методов сортировки, вообще затруднительно и поэтому некоторые характеристики методов получены эмпирическим путем.

3. Простые методы сортировки массивов

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

Описание методов сортировки массивов с некоторой смысловой и стилистической правкой заимствовано в [7].

Иллюстрирующие эти методы программы используют переменную-вектор W, компоненты которого имеют тип Item и их нужно рассортировать in situ, т.е. фрагменты соответствующих раздела типов и раздела переменных выглядят так:

type

Index=1..100; {размерность массива выбрана произвольно}

Item=record

Key : Integer;

, , , {описание других компонент}

end;

Vector=array[Index] of Item;

var

W : Vector;

Сортировка простыми включениями

Этот метод обычно используют игроки в карты. Элементы условно разделяют на готовую последовательность w1, … ,wi-1 и входную последовательность wi, … ,wn. На первом шаге i=2, затем это значение увеличивается на единицу на последующих шагах. На каждом из шагов выбирается первый элемент входной последовательности (т. е wi) и передается в готовую последовательность с помощью вставки (включения) его на подходящее место в соответствии с функцией упорядочения. Процесс продолжается до тех пор, пока величина i не станет равной n, и иллюстрируется рисунком (Рис6.1) на примере последовательности из восьми случайно расположенных одноразрядных чисел. Таким образом, алгоритм сортировки простыми включениями может быть описан так:

for I =2 to N do

begin

X :=W[I].Key;

{вставить x на подходящее место в

w1...wi }

end;

Для поиска подходящего места можно чередовать сравнения и пересылки, т.е. “просеивать” x, сравнивая его с очередным элементом. При просеивании предполагается, что если очередной элемент вектора W[I] >=X, то W[I] сдвигается на одну позицию направо (при первой проверке - на место X). Затем X либо вставляется на “освободившееся” место, либо сравнивается с очередным левым элементом вектора. Просеивание может закончиться при двух различных условиях (найден элемент wk с ключом меньшим, чем ключ wi или достигнут левый конец готовой последовательности).

Это типичный пример цикла с двумя условиями, при оформлении которого желательно использовать фиктивный элемент (барьер), для чего следует расширить диапазон индексов в описании вектора, т.е. описать как W=array[0 .. n] of Item.

Одна из возможных реализаций алгоритма представлена ниже в виде процедуры Straightinsertion.

procedure Straightinsertion;

var

I,J : Index;

X : Item;

begin

for I :=2 to N do

begin

X :=W[I];

W[0] :=X;

J :=I - 1;

while X.Key < A[J].Key do

begin

W[J+1] :=W[J];

J :=J - 1;

end;

W[J+1] :=X

end

end; {Straightinsertion}

Число Сi сравнений ключей при i-м просеивании составляет самое большее - i-1 самое меньшее - 1 и, если предположить, что все перестановки ключей равновероятны, в среднем равно i/2. Число Mi пересылок, учитывая барьер, равно i+2. Поэтому общее число сравнений и пересылок есть:

Cmin=n-1	Mmin=2(n-1)
Cср =1/4(n+n-2)	Mср =(n2+9n-10)
Cmax=1/2(n2+n)-1	Mmax=1/2(n2+3n-4)

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

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

Такой алгоритм сортировки (процедура binaryinsertion) называется сортировкой бинарными включениями.

procedure Binaryinsertion;

var

I,J,L,R,M : Index;

X : Item;

begin

for I :=2 to N do

begin

X :=W[I];

L :=1;

R :=I - 1;

while L<=R do

begin

M:=(L+R) div 2;

if X.Key<W[M].Key

then

R :=M - 1

else

L :=M+1

end;

for J :=I - 1 downto L do

W[J+1] :=W[J];

W[L] :=X

end

end; {Binaryinsertion}

Место включения найдено, если W[I].KeyX.Key<W[I].Key, т.е. интервал поиска в конце должен быть равен 1; это означает, что интервал из i ключей делится пополам (log2 i) раз. Таким образом, C=[log2 i] , i=1, ... ,n.

Величину С можно определить аппроксимируя эту сумму с помощью интеграла:

С= log x dx =n(log n-c1)+c1, где с1=log e= 1.44269... .

Анализируя метод, следует учесть, что при делении интервала поиска пополам c учетом асимметрии бинарного поиска действительное число сравнений для i элементов может быть на 1 больше ожидаемого. В результате места включения в “нижней” части находятся в среднем несколько быстрее, чем в “верхней” части т. е.

C= n(log n - log e 0.5).

Ускорение поиска места включения в “нижней” части дает преимущество в тех случаях, когда элементы изначально далеки от правильного порядка (минимальное число сравнений требуется, если элементы вначале расположены в обратном порядке, а максимальное - если они уже упорядочены). Следовательно, это случай неестественного поведения алгоритма сортировки.

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

Этот пример показывает, что “очевидное улучшение” часто оказывается менее существенным по отношению к ожидаемому , и в некоторых случаях может оказаться ухудшением.

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

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

В основе метода лежит просмотр последовательности с целью выбора элемента с наименьшим ключом, после чего он меняется местами с первым элементом. Эти операции повторяются с оставшимися n-1, затем n-2 элементами последовательности и т. д., пока не останется только один элемент - наибольший. Метод иллюстрируется на ранее применявшихся восьми ключах с помощью рисунка 6.2, а соответствующий ему алгоритм можно описать следующим образом:

for I :=1 to N-1 do

begin

{присвоить k индекс наименьшего элемента из a1, ... ,an};

{поменять местами элементы a1 и ak}

end;

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

Алгоритм сортировки простым выбором описан процедурой Straightselection.

procedure Straightselection;

var

I,J,K : Index;

X : Item;

begin

for I :=1 to N -1 do

begin

K :=I;

X :=W[K];

for J :=I+1 to N do

if W[J].Key <X.Key then

begin

K :=J;

X :=W[J]

end;

W[K] :=W[I];

W[I] :=X

end

end; {Straightselection}

В этом варианте сортировки число сравнений ключей не зависит от их начального порядка. Метод ведет себя менее естественно, чем сортировка простыми включениями. Число сравнений определяется выражением C=1/2(n2 -n). Минимальное число пересылок равно Mmin=3(n-1) в случае изначально упорядоченных ключей и принимает наибольшее значение: Mmax= trunc(n2/4)+3(n-1), если вначале ключи расположены в обратном порядке. Среднее значение величины Мср трудно определить, несмотря на простоту алгоритма. Оно зависит от того, на каком шаге просмотра найден действительно минимальный элемент просматриваемой последовательности ключей. Это значение, взятое в среднем для всех перестановок ключей, число которых равно n!, приближенно определяется величиной:

Мср=n(ln n +), где =0.577216 - эйлерова константа

Таким образом, сортировка простым выбором предпочтительнее сортировки простыми включенями кроме случая, когда ключи заранее рассортированы или почти рассортированы. Тогда сортировка простыми включениями работает несколько быстрее.

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

Классификация методов сортировки недостаточно четко определена. Оба представленных выше метода можно рассматривать как сортировку обменом. Однако под сортировкой простым обменом принято понимать метод, основанный на сравнении и обмене пары соседних элементов при последовательном просмотре массива Рис.6.4. и повторении этих дествий до тех пор, пока не будут рассортированы все элементы.

Если представить массив расположенным вертикально, а его элементы пузырьками в резервуаре с водой и имеющими “вес”, то каждый проход “снизу-вверх” по массиву приводит к “всплыванию” пузырька на соответствующий его весу уровень. Поэтому метод часто называют сортировкой методом пузырька. Реализация его простейшего варианта приведена в пророцедуре Bubblesort и иллюстируется рисунком 6.4.

Procedure Bubblesort;

var

I,J : Index;

X : Item;

begin

for I :=2 to N do

begin

for J :=N downto I do

if A[J - 1].Key > A[J].Key then

begin

X :=A[J-1];

A[J-1] :=A[J];

A[J] :=X;

end;

end;

end;

Этот алгоритм легко усовершенствовать. Пример на Рис.6.4. показывает, что три последних прохода никак не влияют на порядок элементов, поскольку они уже рассортированны. Алгоритм можно усовершенствовать, запоминая факт какого-либо обмена на данном проходе. Если обмена нет, то просмотр можно прекратить. Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и место (индекс) последнего обмена. Действительно, все пары соседних элементов с меньшими индексами, уже расположены в нужном порядке. Поэтому следующие проходы можно закончить на этом индексе.



Кроме того методу свойственна определенная ассиметрия: один неправильно расположенный “пузырек” в “тяжелом” конце рассортированного массива всплывает на свое место за один проход, а неправильно расположенный элемент в “легком” конце будет опускаться только на один шаг на каждом проходе. Например, (при просмотре слева направо) последовательность

12 18 42 44 55 67 94 06

будет отсортирован за один проход, а сортировка последательности

94 06 12 18 42 44 55 67

потребует семи проходов. Асимметрия подсказывает третье улучшение: менять направление следующих один за другим проходов. Использующий это улучшение алгоритм называется шейкер-сортировкой и иллюстрируется рисунком 6.5. Примером реализации метода является процедура Shakesort.

Procedure Shakesort;

var

J,K,L,R : Index;

X : Item;

begin

L :=2;

R :=N;

K :=N;

repeat

for J :=R downto L do

if A[J - 1].Key > A[J].Key then

begin

X :=A[J - 1];

A[J - 1] :=A[J];

A[J] :=X;

K :=J;

end;

L :=K+1;

for J :=L to R do

if A[J - 1].Key > A[J].Key then

begin

X :=A[J - 1];

A[J - 1] :=A[J];

A[J] :=X;

K :=J;

end;

R :=K - 1;

until L > R;

end;

Число сравнений в алгоритме простого обмена постоянно и равно:

C=(n2-n)/2,

а минимальное, среднее и максимальное количество пересылок соответственно равны:

Мmin=0, Мср=(n2-n)*0.75, Мmax=(n2-n)*1.5

Анализ улучшенных методов, особенно метода шейкер-сортировки, довольно сложен. Примерные его оценки сводятся к следующему: среднее число проходов пропорционально n-k1*n1/2, а среднее число сравнений - 1/2((n2-n(k2+ln n), где k1 и k2 - некоторые коэффициенты пропорциональности [14].

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

4. Улучшеные методы сортировки

Все простые методы в общем случае перемещают каждый элемент на одну позицию на каждом элементарном шаге. Поэтому их сложность оценивается порядком n2 таких шагов. С другой стороны, используя статистические оценки, можно показать, что среднее “расстояние”, на которое должен переместиться каждый из n элементов во время сортировки, равно n/3 мест. Таким образом, поиск более эффективных методов сортировки должен основываться на пересылке элементов на большие расстояния и (или) на получении большего количества информации об упорядоченности за один просмотр (последнее очевидно).

Сортировка включениями с убывающим приращением

Усовершенствование сортировки простыми включениями было предложено Д.Л.Шеллом [7]. Метод рассматривается на том же примере из восьми элементов Рис.6.6 и состоит в следующем.

На первом проходе отдельно группируются и сортируются все элементы, отстоящие друг от друга на h позиций. Этот процесс называется h-сортировкой. В примере h=4, каждая группа на рисунке выделена тоном и содержит ровно два элемента, а первый проход - это 4-сортировка.

Затем элементы, отстоящие друг от друга на h/2 позиций, вновь объединяются в группы и снова сортируются (в примере - две позиции и, соответственно, 2-сортировка). На третьем и в рассматриваемом случае последнем проходе все элементы сортируются обычной сортировкой, или 1-сортировкой.

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

В результате применения метода массив окажется упорядоченным при любой последовательности приращений, но конечное приращение должно быть равным единице. Тогда вся сортировка, в худшем случае, будет выполняться на последнем проходе. Более того, метод включения с убывающими приращениями обеспечивает лучшие результаты, если приращения не являются степенями двойки. Поэтому в процедуре, иллюстрирующей метод Шелла, все t приращений обозначаются через h1, h2, ..., ht с условиями ht = 1 и hi+1 < hi.

Каждая h-сортировка программируется как сортировка простыми включениями, причем для упрощения условия окончания цикла поиска места включения используется барьер. Так как каждая h-сортировка требует собственного барьера, а массив w необходимо дополнить не одной компонентой w[0], a t компонентами, т. е. описать как w: array[-t .. n] of item.

Этот алгоритм представлен в виде процедуры Shellsort, для t = 4.

procedure Shellsort;

const

T = 4;

var

I,J,K,S : Index;

M : 1 .. T;

X : Item;

H : array[1 .. T] of Integer;

begin

H[1] := 9;

H[2] := 5;

H[3] := 3;

H[4] := 1;

for M := 1 to T do

begin

K := H[M];

S := -K; {место барьера}

for I := K+1 to N do

begin

X := W[I];

J := I - K;

if S = 0 then

S := -K;

S := S+1;

W[S] := X;

while X.Key < W[J].Key do

begin

W[J+K] := W[J];

J := J - K

end;

W[J+K] := X

end

end

end;

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

На практике обычно используются последовательности приращений, рекомендованные Д.Кнутом [14], (последовательности записаны в обратном порядке):

1, 4, 13, 40, 121, ..., где hk-1 = 3hk + 1, ht = 1 и t = [log3n] - 1,

или

1, 3, 7, 15, 31, ..., где hk-1= 2hk + 1, ht = 1 и t = [log2n] - 1.

Там же отмечается, что в последнем случае затраты, которые требуются для сортировки n элементов с помощью алгоритма Шелла, пропорциональны n1.2.

Сортировка с помощью дерева

Метод сортировки простым выбором основан на выборе наименьшего ключа среди n элементов ( требуется n-1 сравнение), затем среди n-1 элементов (n-2 сравнений) и т.д. Улучшить эту сортировку можно в том случае, если в результате каждого просмотра получать больше информации. Например, с помощью n/2 сравнений можно определить наименьший из каждой пары рядом расположенных ключей. При помощи следующих n/4 сравнений - наименьший из каждой пары наименьших ключей и т.д. Таким образом, при помощи всего n-1 сравнений можно построить дерево выбора Рис.6.7, и определить корень (наименьший ключ).

На втором шаге необходимо спускаться по пути, содержащему наименьший ключ, и, исключая его, последовательно заменять на "пусто", либо на элемент, находящийся на противоположной ветви промежуточного узла, если такая ветвь существует (Рис.6.8.а). Элемент, оказавшийся в корне дерева вновь имеет наименьший среди оставшихся ключ и может быть исключен (Рис.6.8.б). После n таких шагов дерево становится пустым и процесс сортировки заканчивается.

При этом каждый из n шагов требует log2n сравнений. Поэтому вся сортировка требует только n*log2n+n элементарных операций c учетом n шагов, необходимых для построения дерева. Это хорошая оценка в сравнении с простым методом, требующим n2 шагов и даже сортировкой Шелла, которая требует n1.2 шагов, но построение древовидной структуры при реализации метода в “чистом” виде усложняет задачу представления информации и соответственно отдельных шагов.

Кроме того, в “рабочей” версии алгоритма желательно избавиться от необходимости в дырах, которые в конце заполняют все дерево и приводят к большому количеству лишних сравнений, а также найти способ представления дерева из n элементов в n единицах памяти вместо 2n-1 единиц. С этой целью пирамида определяется как последовательность ключей hl, hl+1, ..., hr такая, что hi h2i, hi h2i+1 для всякого i = l, ..., r/2.

Если двоичное дерево представлено в виде массива, как показано на Рис.6.9, то, деревья сортировки на Рис.6.10.а и 6.10.б так же являются пирамидами, и элемент h1 пирамиды есть ее наименьший элемент т.е. h1 = min(h1 ... hn).

Пусть задана пирамида с элементами hl+1,..., hr для некоторых значений l и r, в которую нужно добавить новый элемент х для того, чтобы сформировать расширенную пирамиду hl, ..., hr.

В качестве примера пирамида h1, ..., h7, (Рис.6.10.а) расширяется "влево" и дополняется элементом h1=5. Новый элемент х сначала помещается в вершину дерева, а затем "просеивается" по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх. В примере значение 5 сначала меняется местами с 1, затем с 2, и так формируется дерево, показанное на Рис.6.10.б. Предложенный способ просеивания позволяет сохранить условия, определяющие пирамиду.

Способ построения пирамиды in situ был предложен в[7]. В нем можно использовать процедуру просеивания Sift, приведенную ниже. В ней используется массив h1, ... ,hn, элементы hn/2+1, ... ,hn которого уже образуют пирамиду, поскольку не существует двух индексов i, j, таких. что j = 2i (или j = 2i+1). Эти элементы составляют последовательность, которую можно рассматривать как нижний ряд соответствующего двоичного дерева (см.Рис.6.9), где не требуется никакого упорядочения. Теперь пирамида расширяется влево: на каждом шаге добавляется новый элемент и при помощи просеивания помещается на соответствующее место.

procedure Sift(L,R : Index);

var

I,J : Index;

X : Item;

begin

I := L;

J := 2 * I;

X := A[I];

while J < R do

begin

if J < R then

if A[J].Key > A[J+1].Key then

J := J+1;

if X.Key <= A[J].Key then break;

A[I] := A[J];

I := J;

J := 2 * I

end;

A[I] := X

end; {Sift}

Этот процесс иллюстрируется Рис.6.11 и приводит к пирамиде, показанной на Рис.6.9. Следовательно, процесс построения пирамиды из n элементов in situ можно описать следующим образом:

L := (N div 2)+1;

while L > 1 do

begin

L := L - 1;

Sift(L,N)

end;

Для выполнения условия in situ на каждом шаге из пирамиды выбирается последняя компонента (пусть - х), верхний элемент пирамиды помещается на освободившееся место, а х просеивается на свое место. В этом случае необходимо совершить n-1 шагов, что иллюстрируется рисунком 6.12 и описывается с помощью процедуры sift:

R := N;

while R > 1 do

begin

X := A[1];

A[1] := A[R];

A[R] := X;

R := R - 1;

Sift(L,R)

end;

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

procedure Heapsort;

var L,R: Index;

X : Item;

procedure Sift;

var I,J : Index;

begin

I := L;

J := 2 * I;

X := A[I];

while J <= R do

begin

if J < R then

if A[J].Key < A[J+1].Key then

J := J+1;

if X.Key >= A[J].Key then Break;

A[I] := A[J];

I := J;

J := 2 * I

end ;

A[I] := X

end ;

begin

L := (N div 2) + 1;

R := N;

while L > 1 do

begin

L := L - 1;

Sift

end ;

while R > 1 do

begin

X := A[L];

A[L] := A[R];

A[R] := X;

R := R - 1;

Sift

end

end; {Heapsort}

Сортировка с разделением.

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

Быстрая сортировка основана на том, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Так, если предположить, что заданы n элементов с ключами, расположенными в обратном порядке, то их можно рассортировать, выполнив всего n/2 обменов. Для этого необходимо сначала поменять местами самый левый и самый правый элементы и постепенно продвигаться с двух концов к середине. Этот пример позволяет предложить следующую процедуру: выбрать случайным образом какой-то элемент (пусть x) и просматривать массив, двигаясь слева направо, пока не найдется элемент аi > x, а затем просматривать его справа налево, пока не найдется элемент аj < x. Затем, поменяв местами эти два элемента и продолжить процесс "просмотра с обменом", пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими, чем x, и правую - с ключами большими x. В процедуре Partition, реализующей такое разделение, отношения > и < заменены на >= и <=, отрицания которых в операторе цикла с предусловием - это и есть < и >. При такой замене x действует как барьер для обоих просмотров.

procedure Partition;

var W,X: Item;

begin

I :=L;

J := N;

{выбор случайного элемента X}

repeat

while A[I].Key < X.Key do I := I+1;

while X.Key < A[J].Key do J := J - 1;

if I <= J then

begin

W := A[I];

A[I] := A[J];

A[J] := W;

I := I+1;

J := J - 1

end;

until I > J

end;{Partition}

Если, например, в качестве х выбрать средний ключ, равный 4, из массива ключей

5 6 2 4 8 1 3 7,

то для разделения массива потребуются два обмена: 3 с 5 и 1 с 6. Результатом будет массив

3 1 2 4 8 6 5 7

и конечные значения индексов i = 5 и j = 3. Таким образом, ключи а1, ..., аi-1 меньше или равны ключу х = 4, а ключи аj+1, ..., аn больше или равны х. Следовательно, получены два подмассива

Ak.Key <= X.Key для k = 1, ..., i-1,

Ak.Key > X.Key для k = j+1, ..., n,

причем

Ak.Key = X.Key для k = j+1, ..., i-1.

Теперь для сортировки, разделив массив, нужно повторить ту же процедуру применительно к обеими полученным частями, затем к частями этих частей и т.д., пока каждая часть не будет содержать только один элемент. В таком виде метод может быть реализован процедурой Quicksort, в тексте которой вместо процедуры Partition описана рекурсивная процедура Sort:

procedure Quicksort;

procedure Sort (L,R : Index);

var I,J : Index;

X,W : Item;

begin

I := L; J := R;

X := A[(L+R) div 2];

repeat

while A[I].Key < X.Key do I := I+1;

while X.Key < A[J].Key do J := J - 1;

if I <= J then

begin

W := A[I];

A[I] := A[J];

A[J] := W;

I := I+1;

J := J - 1

end

until I > J;

if L < J then Sort(L,J);

if I < R then Sort(I,R)

end ;

begin

Sort(1,N)

end; {Quicksort}

Поиск медианы

Медианой последовательности из n элементов называется элемент, значение которого меньше (или равно) половины n элементов и больше (или равно) другой половины. Так, в последовательности 5 6 2 4 8 3 1 7 медианой является элемент 4.

Задачу поиска медианы принято связывать с сортировкой, т.к. медиану всегда можно найти, упорядочив n элементов и затем выбрать средний элемент. Но потенциально найти медиану значительно быстрее позволяет разделение, которое выполняет процедура Partition. Кроме того, рассматриваемый ниже метод позволяет решить более общую задачу поиска элемента с k - м по величине значением (квантилей) из n элементов в неупорядоченном массиве.

Процедура поиска медианы сводится к следующему [7]. С помощью операции разделения, которая используется при быстрой сортировке, для l=1, r=n и a[k], выбранного в качестве разделяющего значения х, определяются значения индексов i и j, такие, что a[h]<x для всех h<i, a[h]>x для всех h>j и i>j. При этом возможны три варианта:

Разделяющее значение х было слишком мало. В результате граница между двумя частями оказалась ниже искомого значения k. Тогда процесс разделения следует повторить для элементов a[i], ..., a[r].

Выбранная граница х была слишком велика. Операцию разделения следует повторить для a[l], ..., а[j].

Значение k лежит в интервале j < k < i: элемент a[k] разделяет массив в заданной пропорции и, следовательно, является искомым.

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

. . .

L := 1;

R := N;

while L < R do

begin

X := A[K];

Partition(A[L]...A[R]);

if J < K then L := I;

if K < I then R := J

end;

Учитывая условие окончания поиска, можно сформулировать всю процедуру Find.

procedure Find (K : Integer);

var

L,R,I,J,W,X : Integer;

begin

L := 1;

R := N;

while L < R do

begin

X := A[K];

I := L;

J := R;

repeat {split}

while A[I] < X do

I := I+1;

while X < A[J] do

J := J-1;

if I < J then

begin

W := A[I];

A[I] := A[J];

A[J] := W;

I := I+1;

J := J - 1

end

until I > J;

if J < K then L := I;

if K < I then R := J

end

end; {Find}

Если усредняя предположить, что каждое разбиение вдвое уменьшает размер подмассива, в котором содержится искомый элемент, то число необходимых сравнений равно n+n/2+n/4+ ... +1 = 2n , что предпочтительнее предварительной сортировки всего множества элементов для выбора k-го по величине значения (такой метод, в лучшем случае, дает порядок n*log n). Однако, в худшем случае, когда каждый шаг разбиения уменьшает размер подмассива только на 1, может потребоваться n2 сравнений. В связи с этим алгоритм нецелесообразно применять к коротким (до нескольких десятков компонент) массивам.

5. Сортировка последовательностей

Простое слияние

В отличие от регулярных структур с прямым доступом (массивов), на сортировку последовательностей (файлов) накладывается строгое ограничение: в сортируемых данных на каждом из шагов для просмотра непосредственно доступен только один элемент. Хорошей иллюстрацией этого ограничения может служит пример с игральными картами. В первом случае необходимо сортировать “колоду” карт, разложенных на столе “картинками” вверх (есть прямой доступ к изображению каждой картинки). Во втором случае колода лежит на столе в “собранном” виде, т. е. для просмотра доступна только верхняя карта, которую нужно “в слепую” поместить в какое-то место в колоде. Естественно предположить, что при такой постановке без дополнительных уточнений задача решения не имеет.

В качестве основного метода при сортировке последовательностей используется сортировка слиянием. Слияние означает объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи “скользящего” выбора элементов, доступных для просмотра (видимых в данный момент). Эта процедура достаточно просто реализуется и используется в процессе последовательной сортировки как вспомогательная. Однако при этом дополнительно потребуется наличие хотя бы двух (в начале пустых) последовательностей, чем нарушается условие in situ.

Одна из разновидностей сортировки слиянием называется простым слиянием и состоит в следующем.

Последовательность а разбивается на две половины b и с.

Последовательности b и с сливаются при помощи объединения отдельных элементов в упорядоченные пары.

Полученной последовательности присваивается имя а и повторяются шаги 1 и 2, но теперь упорядоченные пары сливаются в упорядоченные четверки.

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

В качестве примера ниже рассматривается уже знакомая последовательность

5 6 2 4 8 3 1 7.

На первом шаге разбиение дает последовательности

5 6 2 4 и 8 3 1 7.

При слиянии на первом шаге оказываются доступными компоненты 5 и 8, затем 6 и 3 и т. д.

Результатом слияния отдельных компонент с учетом упорядочивания пар будет последовательность

5 8 3 6 1 2 4 7.

Новое разбиение и слияние, но теперь уже упорядоченных пар в упорядоченные четверки позволяют получить последовательность

1 2 5 8 3 4 6 7.

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

Третье разбиение и слияние приводят, наконец, к нужному результату:

1 2 3 4 5 6 7 8.

В приведенном примере сортировка производится за три прохода, каждый проход состоит из фазы разбиения и фазы слияния. Для выполнения сортировки потребуются три “ленты”, на которых могут быть записаны последовательности. Поэтому такой прием сортировки часто называют трехленточным слиянием.

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

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

желанием подчеркнуть тот факт, что сбалансированное слияние является далеко не худшим по критерию временной сложности методом сортировки не только файлов, но и массивов, если не принимать во внимание нарушение условия in situ;

при разработке программы не приходится отвлекаться на оформление “чисто файловых” операций (такая программа в дальнейшем может быть легко модифицирована применительно к файлам);

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

Сбалансированное слияние

Таким образом, вместо двух лент при сбалансированном слиянии будет использован один массив, который рассматривается как последовательность, доступная с обоих “концов”. Для реализации алгоритма понадобиться два таких массива, поскольку для сбалансированного слияния необходимы четыре ленты. Общий вид объединенной фазы слияния-разбиения в этом случае можно изобразить так, как показано на Рис.6.13. Направление пересылки сливаемых элементов здесь меняется после операций с каждой упорядоченной парой на первом проходе, после каждой упорядоченной четверки на втором проходе и т. д.; таким образом равномерно заполняются две выходные последовательности, представленные двумя концами одного массива, в данном случае выходного. После каждого прохода массивы меняются ролями: входной становится выходным и наоборот.

Программу можно еще больше упростить, объединив два различных массива в один массив двойной длины, в результате чего данные будут представлены следующим образом:

type

Vector=array [1..2 * N] of Item;

. . .

var

W : Vector;

. . .

Пусть далее индексы I и J указывают на два исходных элемента, а K и L означают места пересылки (см. Рис.6.13). Исходными данными являются элементы последовательности W1, ..., Wn. Для указания направления пересылки данных используется флажок - булевская переменная Up :Up=True будет означать, что на текущем проходе компоненты W1, ..., Wn будут пересылаться в переменные Wn+1, ..., W2n, тогда как Up=False будет указывать, что Wn+1, ..., W2n должны переписываться в W1, ..., Wn. Значение Up строго чередуется между двумя последовательными проходами. И наконец, вводится переменная P для обозначения длины сливаемых подпоследовательностей (P-наборов). Ее начальное значение равно 1, и оно удваивается перед каждым очередным проходом (для простоты предполагается, что N - всегда степень двойки). С учетом сказанного, первая версия программы простого слияния примет вид:

procedure Mergesort;

var

I,J,K,L : Index;

P : Integer;

Up : Boolean;

begin

Up :=True;

P :=1;

repeat {инициация индексов}

if Up then

begin

I :=1;

J :=N;

K :=N+1;

L :=2 * 1

end

else

begin

K :=1;

L :=N;

I :=N+1;

J :=2 * 1

end;

{слияние p-наборов последовательностей I и J

в последовательности K и L}

Up :=-Up;

P :=2 * P

until P=N

end;{ Mergesort}

Уточняя действие, описанное как комментарий, можно отметить, что проход, обрабатывающий N элементов, состоит из последовательных слияний P-наборов. После каждого отдельного слияния направление пересылки переключается из нижнего в верхний конец выходного массива или наоборот, чтобы обеспечить одинаковое распределение в обоих направлениях. Если сливаемые элементы посылаются в нижний конец массива, то индексом пересылки служит K и K увеличивается на 1 после каждой пересылки элемента. Если же они пересылаются в верхний конец массива, то индексом пересылки является L и l после каждой пересылки уменьшается на 1. Чтобы упростить операцию слияния, можно считать, что место пересылки всегда обозначается через k, и значения k и l меняются местами после слияния каждого р-набора, а приращение индекса обозначается через h, где h равно либо 1, либо -1. С учетом уточнений программа примет вид:

H :=1;

M :=1;

repeat Q :=P;

R :=P;

M :=M - 2 * P;

{слияние Q элементов из I и R элементов из J,

индекс засылки есть K с приращением H};

H :=-H;

{обмен значениями K и L};

until M=0;

На следующем этапе уточнения нужно сформулировать саму операцию слияния. Здесь следует учесть, что остаток последовательности, которая остается непустой после слияния, “приписывается” к выходной последовательности при помощи простого копирования.

while ((Q<>0) and (R<>0)) do

begin {выбор элемента из I или J}

if A[I].Key < A[I].Key

then

begin

{пересылка элемента из I в K, увеличение I и K};

Q:=Q - 1;

end

else

begin

{пересылка элемента из J в K, увеличение J и K};

R:=R - !

end

end;

После уточнения операций копирования остатков программу можно считать законченной. Перед тем как записать ее полностью, желательно устранить ограничение, в соответствии с которым n должно быть степенью двойки. Если n не есть степень двойки, то слияние р-наборов можно продолжать до тех пор, пока длина остатков входных последовательностей не станет меньше р. Это повлияет только на ту часть программы, где определяются значения Q и R - длины последовательностей, которые предстоит сливать. Таким образом, вместо фрагмента

Q := P;

R := P;

M := M-2 * P

можно использовать следующие операторы (M обозначает общее число элементов в двух входных последовательностях, которые осталось слить):

if M >= P then Q := P else Q := M;

M := M-Q;

if M >= P then R := P else R := M;

M := M-R;

Кроме того, чтобы обеспечить окончание выполнения программы, нужно заменить условие P=N, управляющее внешним циклом, на P >= N.

После этих модификаций можно описать весь алгоритм, например, в виде процедуры Mergesort:

procedure Mergesort;

var

I,J,K,L,T : Index;

H,M,P,Q,R : Integer;

Up : Boolean;

begin

Up := True;

P := 1;

repeat

H := 1;

M := N;

if Up

then

begin

I := 1;

J := N;

K := N+1;

L := 2 * N

end

else

begin

K := 1;

L := N;

I := N+1;

J := 2 * N

end ;

repeat {слияние серий из I и J в K}

{Q - длина серии из I, R - длина серии из J}

if M >= P then Q := P else Q := M;

M := M - Q;

if M >= P then R := P else R := M;

M := M - R;

while (Q <> 0) and (R <> 0) do

begin {слияние}

if A[I].Key < A[J].Key

then

begin

A[K] := A[I];

K := K+H;

I := I+1;

Q := Q - 1

end

else

begin

A[K] := A[J];

K := K+H;

J := J - 1;

R := R - 1

end

end ;

{копирование остатка серии из j}

while R <> 0 do

begin

A[K] := A[J];

K := K+H;

J := J - 1;

R := R - 1

end ;

{копирование остатка серии из i}

while Q <> 0 do

begin

A[K] := A[I];

K := K+H;

I := I+1;

Q := Q - 1

end ;

H := -H;

T := K;

K := L;

L := T;

until M = 0;

Up := -Up;

P := 2 * P;

until P >= N;

if -Up then

for I := 1 to N do

A[I] := A[I+N]

end; {Mergesort}

При оценке вычислительной сложности метода нужно учесть следующее. Поскольку на каждом проходе значение P удваивается и сортировка заканчивается, как только P>=N, она требует [log2n] проходов. По определению при каждом проходе все множество из n элементов копируется ровно один раз. Следовательно, общее число пересылок равно M=n*[log2n]. Число сравнений по ключу меньше, чем М, так как при копировании остатка последовательности сравнения не производятся. Здесь, правда, следует учитывать, что применительно к файлам операция сравнения может оказаться сложнее пересылки.

Однако, с такими показателями применительно к массивам, алгоритм сортировки слиянием выдерживает сравнение даже с усовершенствованными методами. Величина затрат времени, характеризующая быстродействие сортировки слиянием и полученная в результате описанного выше эксперимента, содержатся в табл.6.2. Таким образом, ее эффективность уступает быстрой сортировке, но выше, чем у пирамидальной сортировки. Существенным недостатком сортировки слиянием является использование памяти размером 2n элементов, но в рекурсивном варианте быстрой сортировки дополнительные затраты памяти из-за достаточно большой глубины рекурсии могут быть значительно больше.

При этом сортировка методом простого (сбалансированного) слияния также подлежит усовершенствованию. Методы естественного и многоленточного слияния оказываются еще более эффективными. С описанием этих методов и возможных способов их реализации можно ознакомиться в [7.14].

6. Сравнение методов сортировки массивов

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

Пусть n по-прежнему означает число сортируемых элементов, а С и М - соответственно количество необходимых сравнений ключей и пересылок элементов. Для среднестатистической оценки простых методов сортировки можно использовать аналитические формулы [6]. Они приведены в табл.6.8, заголовки столбцов которой определяют соответственно минимальные, максимальные и ожидаемые средние значения для всех n! перестановок из n элементов.

Таблица 6.1 Аналитические оценки простых методов сортировки

	Минимум	Среднее	Максимум
Простые включения	C = n-1 M=2(n-1)	(n2+n-2)/4 (n2-9n-10)/4	(n2-n)/2-1 (n2+3n-4)/2
Простой выбор	C=(n2-n)/2 M=3(n-1)	(n2-n)/2 n(ln n+0,57)	(n2-n)/2 n2/4+3(n-1)
Простой обмен	C=(n2-n)/2 M = 0	(n2-n)/2 (n2-n)*0,75	(n2-n)/2 (n2-n)*1,5

Для усовершенствованных методов достаточно простые и точные формулы неизвестны. В качестве приближенных оценок используются утверждения, что вычислительная сложность пропорциональна ci*n1.2 в случае сортировки Шелла и ci*n*logn в случаях пирамидальной и быстрой сортировок. Известна также классификация алгоритмов сортировки на простые (О=n2) и усовершенствованные или "логарифмические" (О=n*log n).

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

Результаты проведенного эксперимента (ЭВМ типа IBM PC с процессором PENTIUM 100) применительно к рассмотренным алгоритмам сортировки иллюстрируются таблицами 6.хх и 6.хх, смысл которых ясен из заголовков самих таблиц, их строк и столбцов. Кроме того, ниже (только с иллюстративными целями) приведены рисунки, отражающие поведение простых методов, метода Шелла и быстрой сортировки по критерию отношения прямо и обратно упорядоченных элементов исходного массива (без учета распределения длины предварительно упорядоченных цепочек).