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
- RJF2 posted to SAS-L
- Thu, 15 Aug 2002 14:06:57 -0400
- further reading on Wikipedia
/*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)