docs/Shellsort.htm

   1 <HEAD>
   2 <TITLE>Shellsort
   3 </TITLE>
   4 <BODY>
   5 <H2>
   6 <H3>
   7 <A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
   8 <A HREF="../../hbook.html">
   9 <IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
  10 <A HREF="../../sort_a.html">
  11 <IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
  12 <A HREF="../../expand.html">
  13 <IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
  14 <A HREF="414.sort.c.html">
  15 </A>
  16 <A HREF="414.sort.c.html">
  17 <IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
  18 <A HREF="414b.sort.c.html">
  19 <IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
  20 <BR></H2>
  21 <HR>
  22 <H2><B>Shellsort
  23 </B></H2><BR>
  24 <CENTER>
  25 <TABLE BORDER>
  26 <TR>
  27 <TD COLSPAN = 1>
  28 <TD rowspan = 1>
  29 <TR><TD>
  30 <XMP>
  31      procedure sort( var r : ArrayToSort; lo, up : integer );
  32
  33      label     999;
  34      var  d, i, j : integer;
  35           tempr : ArrayEntry;
  36      begin
  37      d := up-lo+1;
  38      while d>1 do begin
  39           if d<5 then    d := 1
  40                else d := trunc( 0.45454*d );
  41           {*** Do linear insertion sort in steps size d ***}
  42           for i:=up-d downto lo do begin
  43                tempr := r[i];
  44                j := i+d;
  45                while j <= up do
  46                     if tempr.k > r[j].k then begin
  47                          r[j-d] := r[j];
  48                          j := j+d
  49                          end
  50                     else goto 999;  {*** break ***}
  51                999:
  52                r[j-d] := tempr
  53                end
  54           end
  55      end;
  56 </XMP></TD></TR></TABLE>
  57 <BR>
  58 <H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/414.sort.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (414.sort.c)  <A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/414.sort.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (414.sort.p)
  59 </H3></CENTER>
  60 <HR><H4>
  61 <IMG SRC="../../images/aw3.gif" align=left><H5><BR>
  62 &copy <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
  63 </H5></H4><HR>
  64 </BODY>