As the first step in the decommissioning of sasCommunity.org the site has been converted to read-only mode.


Here are some tips for How to share your SAS knowledge with your professional network.


Knuth Shell Sort

From sasCommunity
Jump to: navigation, search
/*name: Knuth-Shell-Sort: Sort by Insertion, Shell's method
pg 84
Algorithm D (Diminishing increment sort).
Records R(1), ..., R(N) are rearranged in place;
after sorting is complete, their keys will be in order,
K(1) <= ... <= K(N).
An auxiliary sequence of increments h(t), h(t-1), ..., h(1)
is used to control the sorting process, where h(1) = 1;
proper choice of these increments can significatnly decrease the sorting
time.
This algorithm reduces to algorithm S [straight insertion] when t=1.

D1. [Loop on s.] Perform step D2 for s=t, t-1, ..., 1; then terminate.
D2. [Loop on j.] Set h <- h(s),
                 perform steps D3 through D6 for h < j <= N.
    (We will use a straight insertion method to sort elements that are h
    positions apart, so that K(i) <= K(i+h) for 1 <= i <= N-h.
    Steps D3 through D6 are essentially the same as steps S2 through S5,
    respectively in Algorithm S.)

S1. [Loop on j.] Performs steps S2 through S5
    for j= 2, 3, ..., N;
    then terminate the algorithm.
X1. [Loop on i.] Perform steps X2, S3 through S4
    for i <- j-1, j-2, ..., 1
X2    temp <- Var(j)
D3: [Set up i, K, R.] Set i <- j-h, K <- K(j), R <- R(j).
S2. [Set up i, K, R.] Set i <- j-1, K <- K(j), R <- R(j).
    difference:                  ^
    (In the following steps we will attempt to insert R
    into the correct position, by comparing K with K(i)
    for decreasing values of i.)
D4:
S3. [Compare K, K(i).] If K >= K(i), go to step S5.
                                                D6;
    (We have found the desired position for record R.)
D5:
S4. [Move R(i), decrease i.]
    Set R(i+1) <- R(i), then i <- i - 1.
    Set R(i+h) <- R(i), then i <- i - h.
    If i >0, go back to step S3:D4.
    (If i = 0, K is the smallest key found so far,
    so record R belongs in position 1.)
D6:
S5. [R into R(i+1).] Set R(i+1) <- R.
    [R into R(i+h).] Set R(i+h) <- R.
long discussion on choosing increments
first increment should not be greater than N/3
Knuth recommends optimum series to be: (3**k - 1)/2
data _null_;put '%LET INCRMNTS=' @;
 do k=10 to 1 by -1;S=(3**k - 1)/2;put S +(-1)',' @;end;put +(-1) ';';run;
SAS NOTES:
/**************************************************************************/
%Let N_Vars=16;
%Let T_Len = 3;
%*note: first increment should be LE N/3;
*Let Incrmnts=2049,1025,513,257,129,65,33,17,9,5,3,1;*2**i + 1;
*Let Incrmnts=2584,1597,987,610,377,233,144,89,55,34,21,13,8,5,3,2,1;
     *Finonacci series;
%Let Incrmnts=3280,1093,364,121,40,13,4,1;*Knuth's recommended series;
*Let Incrmnts=5,3,2,1;*Finonacci series;
%Let Incrmnts=4,1;

DATA   Work.Sorted_Words;
attrib H       length = 4
       I       length = 4
       J       length = 4
       TempCol length =$4;
array  Col (&N_Vars.) $;
drop   H I J TempCol;

input  Col1  Col2  Col3  Col4  Col5  Col6 Col7 Col8 Col9 Col10
       Col11 Col12 Col13 Col14 Col15 Col16;

*D1;
do H = &Incrmnts;
   *S1;
   do J = H+1 to &N_Vars.;
      *X2;
      tempCol = Col(J);
      *X1;
      do I = J-H to 1 by -H;
         *D4: S3;
         if tempCol >= Col(I) then leave; *goto S5;
         else Col(I+H) = Col(I);
         end;
      *S5:;
      Col(I+H) = tempCol;
      end;
   end;
cards;
503 087 512 908 897 061 275 653 426 154 170 612 677 765 703 509
087 503 512 061 908 170 897 275 653 426 154 509 612 677 765 703
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
;
run;
PROC Print data = Work.Sorted_Words;
run;

--macro maven == the radical programmer 17:06, 31 December 2008 (EST)

See also