Сортировка элементов массива
Предполагается, что сортируемые данные размещаются в массиве записей, каждая
из которых содержит ключ (он определяющий порядок сортировки) и некоторые
сопутствующие данные. Предполагается также наличие функции сравнения двух ключей
(оператора "меньше" или "меньше или равно"). Сопутствующие данные никак не влияют
на порядок сортировки и могут не рассматриваться. Действительно, можно определить
второй массив целых, элементы которого указывают на элементы первого массива,
затем сортировать только его:
<![CDATA[
struct Data
...
end
Data Buff[...]; // Данные
int N; // Число элементов
int dComp(Data @A, @B); // Функция сравнения (A меньше B или нет?)
int Indx[...]; // Индекс
int iComp(int I, J)
return dComp(@Buff[Indx[I]], @Buff[Indx[J]]);
end
]]>
Массив Indx инициализируется последовательностью 0, 1, 2, ..., (N-1) и сортируется
в порядке, определяемом iComp. Результат - Buff[Indx[I]]. Другое (и на самом деле
более серьезное) соображение состоит в том, что функция сортировки массива целых
элементарно преобразуется в функцию сортировки массива записей произвольного типа.
А если язык поддерживает шаблоны функций, то это преобразование выполняется
автоматически. На на языке C++ это выглядит так:
<![CDATA[
template <class T>
void Sort(int N, T Buff[]);
]]>
Итак, дан массив целых Buff, функция сравнения Comp (оператор сравнения < или <=),
требуется написать функцию сортировки Sort:
<![CDATA[
void Sort(int N; int @Buff);
]]>
Придумано довольно много алгоритмов сортировки, они отличаются различным быстродействием
и требуют различного объема дополнительной памяти. Еще один критерий сравнения - устойчивость
в смысле сохранения исходного порядка одинаковых ключей. Приведенный список не претендует на
полноту, но думаю, основные классы алгоритмов в нем представлены:
Алгоритм быстрой сортировки предложил C.A.R.Hoare, cортировку с помощью кучи - J.W.J.Williams,
а сортировку подсчетом - H.H.Seward. Алгоритм сортировки слиянием связывают с именем Джона фон
Неймана, указать авторство остальных ('очевидных') алгоритмов не представляется возможным. Все
эти алгоритмы достаточно старые - к середине 60-х годов они были известны.
Сортировка отбором (selection sort)
'Очевидный' алгоритм сортировки - перебором находится наименьший элемент, он
меняется местами с элементом, стоящим на нулевом месте, затем находится наименьший
среди оставшихся и меняется местами с элементом, стоящим на первом месте... Цикл
заканчивается когда будут выбраны все элементы:
<![CDATA[
void sSort(int N; int @Buff)
int I=0;
while I+1<N do
int M=I;
int J=I+1;
while J<N do
if !(Buff[M]<=Buff[J]) then
M=J;
end
inc J;
end
int Temp=Buff[I];
Buff[I] =Buff[M];
Buff[M] =Temp;
inc I;
end
end
]]>
Этот алгоритм отличается небольшим числом перестановок (N-1) (операций перемещения
данных в три раза больше - 3*(N-1)), но число сравнений очень велико - N*(N-1)/2.
Сортировка вставками (insertion sort)
Сортируемый масив просматривается в порядке возрастания номеров и каждый элемент
вставляется в уже просмотренную часть массива так, чтобы сохранить порядок. На
каждом шаге сортировки часть массива уже упорядочена, поэтому для поиска места
вставки можно использовать метод половинного деления:
<![CDATA[
void iSort(int N; int @Buff)
int I=1;
while I<N do
int J=0;
int K=I;
while J<K do
int M=(J+K)/2;
if Buff[M]<=Buff[I] then
J=M+1;
else
K=M;
end
end
int Temp=Buff[I];
K=I;
while K>J do
Buff[K]=Buff[K-1];
dec K;
end
Buff[K]=Temp;
inc I;
end
end
]]>
Число сравнений значительно меньше, чем при сортировке отбором (<N*Log(N)),
Число перемещений данных в худшем случае N*(N+3)/2.
Пузырьковая сортировка (bubble sort)
Наверное, самый короткий алгоритм сортировки, но и один из самых медленных:
<![CDATA[
void bSort(int N; int @Buff)
while N>0 do
dec N;
int I=0;
while I<N do
if !(Buff[I]<=Buff[I+1]) then
int Temp =Buff[I+1];
Buff[I+1]=Buff[I];
Buff[I] =Temp;
end
inc I;
end
end
end
]]>
Число сравнений всегда N*(N-1)/2, число перестановок в худшем случае такое же
(3*N*(N-1)/2 перемещений данных).
Сортировка слиянием (merge sort)
'Divide-and-conquer' - 'разделяй и властвуй' - исходный массив делится
пополам, каждая половинка упорядочивается, затем производится слияние. Для
сортировки половинок используется та же функция, что и для сортировки всего
массива, функция слияния выделена для экономии места в стеке:
<![CDATA[
void Merge(int L, H; int @Buff) // слияние половинок
int Temp[8000];
int M=(L+H)/2;
int I=L;
int K=0;
while I<M do
Temp[K]=Buff[I];
inc K;
inc I;
end
I=0;
while I<K & M<H do
if Temp[I]<=Buff[M] then
Buff[L]=Temp[I];
inc I;
else
Buff[L]=Buff[M];
inc M;
end
inc L;
end
while I<K do
Buff[L]=Temp[I];
inc L;
inc I;
end
end
void mSort(int L, H; int @Buff)
if H-L<2 then
return
end
if H-L<3 then
if !(Buff[L]<=Buff[L+1]) then
int Temp =Buff[L];
Buff[L] =Buff[L+1];
Buff[L+1]=Temp;
end
return
end
int M=(L+H)/2;
mSort(L,M,@Buff);
mSort(M,H,@Buff);
Merge(L,H,@Buff);
end
]]>
Это быстродействующий алгоритм (~N*Log(N) сравнений и перемещений данных),
но для его работы необходим дополнительный массив, длина которого равна
половине длины сортируемого массива.
Сходная идея используется в алгоритме распределения/слияния:
<![CDATA[
void dSort(int N; int @Buff)
int Left [16000];
int Right[16000];
repeat
byte F=0;
int L=0;
int R=0;
int I=0;
Left [L]=Buff[I];
inc L;
inc I;
while I<N do // распределение
if !(Buff[I-1]<=Buff[I]) then
F=(F+1)%2;
end
if F=0 then
Left [L]=Buff[I];
inc L;
else
Right[R]=Buff[I];
inc R;
end
inc I;
end
int J=0;
int K=0;
I=0;
while J<L & K<R do // слияние
int L1=Left [J];
int R1=Right[K];
while J<L & K<R do
select
case L1<=Left[J] & (!(R1<=Right[K]) | Left[J]<=Right[K]):
L1 =Left[J];
Buff[I]=L1;
inc J;
case R1<=Right[K]:
R1 =Right[K];
Buff[I]=R1;
inc K;
default:
exit
end
inc I;
end
end
while J<L do
Buff[I]=Left [J];
inc I;
inc J;
end
while K<R do
Buff[I]=Right[K];
inc I;
inc K;
end
until L=0 | R=0;
end
]]>
Этот нерекурсивный алгоритм обладает меньшим быстродействием, чем алгоритм
сортировки слиянием (но порядок роста такой же) и для его работы требуется
два дополнительных массива той же длины, что и упорядочиваемый (в принципе
можно обойтись одним, но это несколько сложнее - его надо заполнять с обоих
концов). Зато алгоритм удобен для сортировки записей в файлах, т.к. не требует
произвольного доступа к этим записям. Возможно, при работе с диском это и не
очень важно, но во времена ленточных накопителей это было существенно. Для
повышения быстродействия можно делить исходный набор данных и на большее число
частей.
Сортировка с помощью кучи (heap sort)
Этот алгоритм почти также эффективен, как сортировка слиянием и он не
требует дополнительной памяти. Но вот назвать его очевидным вряд ли можно...
Алгоритм основан на том, что сортируемому массиву может быть поставлено
в соответствие двоичное дерево, каждый узел которого соответствует одному
элементу массива с некоторым номером k и этот узел содержит ссылки на два
других узла, соответствующих элементам с номерами 2*k+1 и 2*k+2. Корень
дерева соответствует элементу с номером 0 (ноль).
Так определенная структура действительно является двоичным деревом и все
элементы массива входят в него. Предположим, что это не так и некоторому
элементу m не соответствует никакой узел дерева. Тогда и элементу n=(m-1)/2
не соответствует никакой узел дерева (иначе приходим к противоречию, т.к.
m=2*n+1 или m=2*n+2). Продолжая рассуждение придем к тому, что элемент
с номером 0 (т.е. корень дерева) не входит дерево, опять противоречие.
Далее, допустим, что на некоторый элемент k имеются ссылки из узлов с различными
номерами p и q (без ограничения общности q>p, т.е. q=p+r, r>=1):
<![CDATA[
k=2*p+s, s=1 или s=2
k=2*q+t=2*(p+r)+t=2*p+2*r+t=(k-s)+2*r+t=k+(2*r+t-s)>=k+1, т.е. k>=k+1
]]>
Противоречие доказывает, что построенная структура является двоичным деревом.
Дальнейшие действия следующие - массив переупорядочивается так, чтобы для
любого k выполнялись неравенства:
<![CDATA[
Buff[k]>=Buff[2*k+1]
Buff[k]>=Buff[2*k+2]
]]>
Затем массив еще раз переупорядочивается, уже по возрастанию номеров. Каждый из
этих шагов требует ~N*log(N) операций. 'Очевидная' реализация может быть такой:
<![CDATA[
int Find(int I; int M; int N; int @Buff) // поиск максимального элемента
if I<N then
int L=Find(2*I+1,M,N,@Buff);
int R=Find(2*I+2,M,N,@Buff);
if Buff[M]<Buff[L] then
M=L;
end
if Buff[M]<Buff[R] then
M=R;
end
if Buff[M]<Buff[I] then
M=I;
end
end
return M;
end
void Heap(int I; int N; int @Buff) // построение кучи
if I<N then
int M=Find(I,I,N,@Buff);
int Temp=Buff[I];
Buff[I] =Buff[M];
Buff[M] =Temp;
Heap(2*I+1,N,@Buff);
Heap(2*I+2,N,@Buff);
end
end
void Sort(int N; int @Buff) // сортировка
Heap(0,N,@Buff);
while N>0 do // переупорядочивание кучи
dec N;
int Temp=Buff[N];
Buff[N] =Buff[0];
Buff[0] =Temp;
int I=0;
while TRUE do // восстановление кучи
int J=2*I+1;
if !(J<N) then
exit
end
if J+1<N then
if Buff[J]<Buff[J+1] then
inc J;
end
end
if !(Buff[I]<Buff[J]) then
exit
end
Temp =Buff[J];
Buff[J]=Buff[I];
Buff[I]=Temp;
I=J;
end
end
end
]]>
Цикл, подобный циклу восстановления кучи может быть использован и для
построения кучи из неупорядоченного массива. В результате приходим к
нерекурсивному алгоритму:
<![CDATA[
void hSort(int N; int @Buff)
int K=N;
while K>0 do
dec K;
int I=K;
while TRUE do
int J=2*I+1;
if !(J<N) then
exit
end
if J+1<N then
if Buff[J]<Buff[J+1] then
inc J;
end
end
if !(Buff[I]<Buff[J]) then
exit
end
int Temp=Buff[J];
Buff[J]=Buff[I];
Buff[I]=Temp;
I=J;
end
end
while N>1 do
dec N;
int Temp=Buff[N];
Buff[N] =Buff[0];
Buff[0] =Temp;
int I=0;
while TRUE do
int J=2*I+1;
if !(J<N) then
exit
end
if J+1<N then
if Buff[J]<Buff[J+1] then
inc J;
end
end
if !(Buff[I]<Buff[J]) then
exit
end
Temp =Buff[J];
Buff[J]=Buff[I];
Buff[I]=Temp;
I=J;
end
end
end
]]>
Естественно, такой алгоритм работает быстрее и требует меньше памяти, но,
наверное, он еще менее очевиден, чем рекурсивный.
Быстрая сортировка (quick sort)
Алгоритм основан на разделениии сортируемого массива на части и перестановке элементов
таким образом, чтобы элементы в левой части массива не превосходили элементов в правой.
На каждом шаге выбирается 'средний' элемент массива, в результате ряда перестановок он
занимает свое свое законное место, затем каждая из частей упорядочивается:
<![CDATA[
void qSort(int L, H; int @Buff)
if H<=L+1 then
return
end
int I=L;
int J=H-1;
int K=(L+H)/2;
while TRUE do
while I<K & Buff[I]<=Buff[K] do
inc I;
end
while J>K & Buff[K]<=Buff[J] do
dec J;
end
if I=J then
exit
end
int Temp=Buff[I];
Buff[I]=Buff[J];
Buff[J]=Temp;
select
case I=K:
K=J;
case J=K:
K=I;
end
end
qSort(L, K,@Buff);
qSort(K+1,H,@Buff);
end
]]>
Если 'средние' элементы находится не слишком далеко от своих законных мест, все
хорошо - оценка времени выполнения ~N*Log(N) (~N+2*N/2+4*N/4+...+N*1), но можно
так упорядочить элементы исходного массива, что 'быстрая' сортировка потребует
~N*N операций и, что еще хуже, N фреймов стека. Следующая функция заполняет
массив самым неблагоприятным для qSort способом:
<![CDATA[
void Fill(int N; int @Buff)
if N>0 then
dec N;
Fill(N,@Buff);
int M=(N+1)/2;
Buff[N]=Buff[M];
Buff[M]=N;
end
end
]]>
В более сложных реализациях алгоритма 'средний' элемент выбирается как
средний из трех или случайным образом. Но как минимум, необходимо заменить
один из рекурсивных вызовов циклом, это предотвратит разрушение стека:
<![CDATA[
void qSort(int L, H; int @Buff)
while TRUE do
if H<=L+1 then
return
end
int I=L;
int J=H-1;
int K=(L+H)/2;
while TRUE do
while I<K & Buff[I]<=Buff[K] do
inc I;
end
while J>K & Buff[K]<=Buff[J] do
dec J;
end
if I=J then
exit
end
int Temp=Buff[I];
Buff[I]=Buff[J];
Buff[J]=Temp;
select
case I=K:
K=J;
case J=K:
K=I;
end
end
if K-L<H-K then
qSort(L, K,@Buff);
L=K+1;
else
qSort(K+1,H,@Buff);
H=K;
end
end
end
]]>
Сортировка подсчетом (counting sort)
Неуниверсальный алгоритм, использующий дополнительную память и выполняющий
сортировку за время, пропорциональное числу элементов массива. Для его
реализации необходимо взаимно однозначно сопоставить каждому возможному
значению элемента массива целое неотрицательное число и нужно, чтобы
максимальное из этих чисел не превосходило значительно числа элементов
массива. Тогда имеет смысл следующий алгоритм:
<![CDATA[
void cSort(int N; int @Buff)
int Temp [16000];
int Tabl [16000];
int M;
int I;
M=0;
I=0;
while I<N do
if M<Buff[I] then
M=Buff[I];
end
Temp[I]=Buff[I];
inc I;
end
inc M;
I=0;
while I<M do
Tabl[I]=0;
inc I;
end
I=0;
while I<N do
inc Tabl[Temp[I]];
inc I;
end
int P;
int Q;
P=0;
I=0;
while I<M do
Q =P;
P =P+Tabl[I];
Tabl[I]=Q;
inc I;
end
I=0;
while I<N do
Buff[Tabl[Temp[I]]]=Temp[I];
inc Tabl[Temp[I]];
inc I;
end
end
]]>
В этой функции нет ни вложенных циклов, ни рекурсивных вызовов. В ней также
нет сравнений элементов между собой. Если ширина диапазона значений элементов
массива не превосходит числа элементов, время сортировки линейно зависит от
числа элементов массива.
Алгоритм может быть использован и в случае, когда ширина диапазона значений
элементов массива значительно превосходит число элементов. Очевидно, любой
ключ представляется послебовательностью байт. Можно разделить ключ на группы
и последовательно упрорядочить массив по каждой из групп. Время сортировки
в этом случае пропорционально произведению числа элементов на число групп.
Например, если дан массив строк, каждая строка может быть разбита на группы
по два символа. Максимальное значение ключа в группе не превосходит 65535
(2**16-1).
Алгоритм эффективен только для очень больших массивов.
Сайт создан в системе
uCoz