Сортировка больших массивов
Говорят, и это подтверждается многочисленными примерами, что 90% времени работы программы.приходится на так называемые узкие места, занимающие в общем объеме программы не более 10% команд. Поиск таких мест и улучшение их временных характеристик — один из основных методов совершенствования программ.
К числу таких узких мест относятся фрагменты программ, занимающиеся упорядочением достаточно объемной информации, поиском данных в больших массивах и т. п. Ниже приводится описание нескольких довольно популярных методов упорядочения числовых массивов и тексты реализующих их процедур. Схемы программ на Си заимствованы из [12], однако в их тексты внесены небольшие изменения. Желающим познакомиться более подробно с другими методами сортировки и возникающими при этом серьезными математическими проблемами мы рекомендуем книгу Д. Кнута "Искусство программирования для ЭВМ", т. 3.
Пузырьковая сортировка (bubble)
Идея этого метода заключается в сравнении двух соседних элементов массива, в результате которого меньшее число (более легкий пузырек) перемещается на одну позицию влево. Обычно такой просмотр организуют с конца массива и после первого прохода самое маленькое число перемещается на первое место. Затем все повторяется от конца массива до второго элемента и т. д.
Известна и другая разновидность обменной сортировки (bubble1), при которой также сравниваются два соседа и, если хотя бы одна из смежных пар была переставлена, просмотр начинают с самого начала. Так продолжают до тех пор, пока очередной просмотр не закончится без перестановок.
С целью повышения быстродействия программ на Си наиболее активно используемые переменные i и j распределяются в регистровой памяти.
Подпрограмма bubble.bas
SUB BUBBLE(X(),N)
FOR 1=1 TO N-l
FOR J=N-1 TO I STEP -1
IF X(J-l) > X(J) THEN
TMP=X(J-1): X(J-l) =X(J): X(J)=TMP
END IF
NEXT J
NEXT I
END SUB
Подпрограмма bubbiei.bas
SUB BUBBLE1(X(),N) M:Q=0
FOR 1=1 TO N-l
IF X(I-l) > X(I) THEN
TMP=X(I-1): X(I-1)=X(I): X(I)=TMP: Q=l
END IF
NEXT I
IF Q=l THEN GOTO *M
END SUB
Функция bubble.с
void bubble(int *x, int n) {
register int i,j;
int tmp;
for(i=l; i<n; i++)
for(j=n-l; j>=i; j—)
if<x[j-l] > x[j])
{
tmp=x[j-1] ;
x[j-l] = x[j];
x[j ] = tmp; } }
Функция bubblel.c
void bubblel(int *x, int n) {
register int i,j;
int tmp,q; m:q=0;
for(i=0; i<n-l; i++)
if(x[i] > x[i+l]) {
tmp=x[i];
x[i]=x[i+l];
x[i+l]=tmp;
q=l; }
if(q!=0) goto m; }
Процедура bubble.pas
procedure bubble(var x:array of integer;n:integer);
var
i,j,tmp:integer;
begin
for i:=l to n-1 do
for j:=n-l downto i do
if x[j]<x[j-l] then begin
tmp:=x[j-l]; x[j-l]:=x[j];
x[j]:=tmp;
end;
end;
Процедура bubblel.pas
procedure bubblel(var x:array of integer;n:integer);
label m;
var
i,tmp,q:integer;
begin m:q:=0
for i:=0 to n-2 do
if x[i] > x[i+l] then begin
tmp:=x[i];
x[i]:=x[i+l];
x [i+1] :=tmp;
q:=l; end;
if q=l then goto m;
end;
Сортировка методом отбора (select)
Идея метода отбора заключается в следующем. Находится элемент с наименьшим значением и меняется местами с первым элементом. Среди оставшихся ищется наименьший, который меняется со вторым, и т. д.
Подпрограмма select.bas
SUB SELECT(X(),N)
FOR I=0 TO N-2
Q=0: K=I: TMP=X(I)
FOR J=I+1 TO N-l
IF X(J)<TMP THEN K=J: TMP=X(J): Q=l NEXT J
IF Q=l THEN X(K)=X(I): X(I)=TMP NEXT I
END SUB
Функция select.с
void select(int *x, int n) {
register int i,j,k;
int q,tmp;
for(i=0; i<n-l; i++) {
q=0;
k=i;
tmp=x[ i ] ;
for(j=i+l; j<n; j++) {
if(x[j] < tmp) {
k=j;
tmp=x[ j ] ;
q=l; } } if (q)
{x[k]=x[i];
x[i]=tmp;} } }
Процедура select.pas
procedure select(var x:array of integer;n:integer);
var
i,j,k,q,tmp:integer;
begin
for i:=0 to n-2 do begin
q:=0;
k:=i;
tmp:=x[i];
for j:=i+l to n-1 do
if x[j]<tmp then begin
k:=j;
tmp:=x[j];
q:=l;
end;
if q=l then begin
x[k]:=x[i];
x[i]:=tmp;
end;
end;
end;
Сортировка методом вставки (insert)
Идея этого метода базируется на последовательном пополнении ранее упорядоченных элементов. На первом шаге сортируются первые два элемента. Затем на свое место среди них вставляется третий элемент. К трем упорядоченным элементам добавляется четвертый, который занимает свое место в новой четверке. И так продолжается до тех пор, пока к n-1 ранее упорядоченным элементам не присоединится последний. Примерно таким способом игроки упорядочивают свои карты при сдаче их по одной.
Подпрограмма insert.bas
SUB INSERT(X%(),N%) DIM I,J,TMP
FOR I=1 TO N-l TMP=X(I)
FOR J=I-1 TO 0 STEP -1
IF TMP > X(J) THEN EXIT FOR
X(J+1)=X(J)
NEXT В X(J+1)=TMP
NEXT I
END SUB
Функция insert.c
void insert(int *x,int n) {
register int i,j; int trnp;
for(i=l; i<n; i++) {
tmp=x[ i ] ;
for(j=i-l;j>=0 && tmp < x[j]; j--)
x[j+l]=x[j];
x[j+l]=tmp;
} }
Процедура insert.pas
procedure insert(var x:array of integer;n:integer);
var
i,j,tmp:integer;
begin
for i:=l to n-1 do
begin
tmp:=x[i];
j:=i-l;
while (j>=0) and (tmp<x[j]> do
begin .
x[j+l]:=x[j]; j:=j-l;
end;
x [ j+1] :=tmp;
end;
end;
Сортировка методом Шелла (shell)
Метод Д. Л. Шелла, опубликованный в 1959 г., предлагает сортировать массив в несколько этапов. На первом этапе в сортировке участвуют достаточно далекие элементы, например, отстоящие друг от друга на восемь позиций. На втором проходе сортируются элементы, расстояние между которыми уменьшено, например до четырех. Затем упорядочиваются каждые вторые элементы и, наконец, на последнем этапе сравниваются смежные элементы. Выбор последовательно уменьшающихся шагов в методе Шелла представляет довольно сложную математическую задачу. На практике чаще всего применяют пятизвенную схему 9—>5—>3—>2—>1.
Подпрограмма shell.bas
SUB SHELLSORT (X%"() , N% )
DIM I, J,GAP,K,XX,A(5) A(0)=9: A(l)=5: A(2)=3: A(3)=2: A(4)=l
FOR K=0 TO 4 GAP=A(K)
FOR I=GAP TO N-1 XX=X(I)
FOR J=I-GAP TO 0 STEP -GAP
IF XX >= X(J) THEN EXIT FOR
X(J+GAP)=X(J)
NEXT J X(J+GAP)=XX
NEXT I
NEXT К
END SUB
Функция shell.с
void shell(int *x,int n) {
register int i,j,gap,k; int xx;
char a[5]={9,5,3,2,l};
for(k=0; k<5; k++) {
gap=a[k];
for(i=gap; i<n; ++i) {
xx=x[i];
for(j=i-gap; xx < x[j] && j >= 0; j=j-gap)
x[j+gap]=x[j); x[j+gap]=xx; } } }
Процедура shell.pas
procedure shell(var x:array of integer;n:integer) ;
var
i,j,k,gap,xx:integer;
const
a:array [0..4] of byte=(9,5,3,2,1};
begin
for k:=0 to 4 do
begin
gap:=a[k];
for i:=gap to n-1 do begin
xx:=x[i];
j:=i-gap;
while (j >= 0) and (xx < x[j]) do
begin
x[j+gap]:=x[j];
j:=j-gap;
end;
x[j+gap]:=xx;
end;
end;
end;
Сортировка методом Хоара (quicksort)
Метод Ч. Э. Р. Хоара, опубликованный в 1962 г., издалека напоминает способ ловли льва в пустыне "методом Вейерштрасса". Сначала пустыню делят пополам и выбирают ту половину, в которой находится лев. Затем эту половину снова делят пополам и так продолжают до тех пор, пока область, содержащая льва, не помещается в клетку. В математике подобный метод применяют для нахождения корня функции, принимающей на концах отрезка разные знаки. Это и есть метод Вейерштрасса, более известный под названием "метода деления пополам".
Хоар применил подобный подход к сортировке и предложил следующий алгоритм. Выберем какой-то средний элемент последовательности хх (обычно в качестве такового выбирают средний элемент). Если он стоит на своем месте (имеется в виду ситуация, когда последовательность упорядочена), то все элементы, расположенные левее, не больше хх, а элементы, находящиеся правее, — не меньше хх. Поэтому первый шаг быстрой сортировки заключается в том, чтобы перенести в левую часть массива те элементы правой половины, которые меньше хх, а в правую часть — те элементы из левой половины, которые больше хх. Обычно при этом поиск ведут в обе стороны от хх и как только обнаруживают пару, нарушающую порядок, производят обмен.
Затем аналогичный прием применяют к каждой из полученных половин. В каждой из них выбирается свой средний элемент и относительно него осуществляются необходимые перестановки. Как следует из описания, алгоритм Хоара очень хорошо укладывается в понятие рекурсивной процедуры. Для единообразия в обращении процедура быстрой сортировки представлена в виде двух процедур — внешней hoar, к которой обращается пользователь, и внутренней — quick. Последняя выполняет рекурсивную обработку подмассива, заданного граничными значениями индексов — left и right.
Подпрограмма hoare.bas
SUB HOARE(X% (),N%)
QUICK X%(),0,N%-1
END SUB
SUB QUICK(X%(),LEFT%,RIGHT%)
DIM I,J,XX,YY
I=LEFT%: J=RIGHT%
XX=X((LEFT%+RIGHT%)\2)
DO
WHILE X%(I) < XX AND I < RIGHT%: I=I+1: WEND
WHILE XX < X%(J) AND J > LEFT%: J=J-1: WEND
IF I <= J THEN
YY=X%(I): X%(I)=X%(J): X%(J)=YY: 1=1+1: J=J-1
END IF
LOOP WHILE I <= J
IF LEFT% < J THEN QUICK X%(),LEFT%,J
IF I < RIGHT% THEN QUICK X%(),I,RIGHT%
END SUB
Функция hoare.c
void hoare(int *x,int n) {
quick(x,0,n-1);
return;
}
/*--------------------------------*/
void quick(int *x, int left, int right) {
register int i,j;
int xx,tmp;
i=left;
j=right;
xx=x[(left+right)/2];
do
{
while (x[i] < xx && i < right) i++;
while (xx < x[j] && j > left) j--;
if (i<=j)
{
tmp=x[ i ] ;
x[i]=x[j];
x[j]=tmp;
i++; j-- ;
}
}
while(i<=j);
if(left < j) quick(x,left,j);
if(i < right) quick(x,i,right);
}
Процедура hoare.pas
procedure quick(var x:array of integer;left,right:integer);
var
i,j,xx,tmp:integer;
begin
i:=left; j:=right;
xx:=x[(left+right) div 2];
repeat
while (x[i] < xx) and (i < right) do i:=i+l;
while (xx < x[j]) and (j > left) do j:=j-l;
if i<=j then
begin
tmp:=x[i];
x[i]:=x [j];
x[j]:=tmp;
i:=i+l;
j:=j-i;
end;
until i>j;
if left < j then quick(x,left,j);
if i < right then quick(x,i,right);
end;
procedure hoare(var x:array of integer;n:integer);
begin
quick(x,0,n-l);
end;
