Практика программирования (Бейсик, Си, Паскаль)




Сортировка больших массивов - часть 3


Идея этого метода базируется на последовательном пополнении ранее упорядоченных элементов. На первом шаге сортируются первые два элемента. Затем на свое место среди них вставляется третий элемент. К трем упорядоченным элементам добавляется четвертый, который занимает свое место в новой четверке. И так продолжается до тех пор, пока к 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




Содержание  Назад  Вперед