'*****************************************************
'*      Sorting an array with the Shell method       *
'* ------------------------------------------------- *
'* REFERENCE:                                        *
'* "NUMERICAL RECIPES By W.H. Press, B.P. Flannery,  *
'*  S.A. Teukolsky and W.T. Vetterling, Cambridge    *
'*  University Press, 1986" [BIBLI 08].              *
'*                                                   *
'*                      Basic Version By J-P Moreau  *
'*                           (www.jpmoreau.fr)       *
'* ------------------------------------------------- *
'* SAMPLE RUN:                                       *
'*                                                   *
'* Table to be sorted:                               *
'*                                                   *
'*  925  518  215  447  948  405   23  886  809  398 *
'*  195  651  451  251  477   78  389  472  774  291 *
'*  942  885  157  143  623   57  183  766  576  888 *
'*   22  145  143  903  128  398  938   58  426  674 *
'*   32   88  269  845  104  711  628  417  671  226 *
'*  266  324  763  298  871  538  639  991  386  652 *
'*  408  331   19  874  680  952  672   92  576  624 *
'*  760  936  735  712  676   14  163  847  367  731 *
'*                                                   *
'*  Sorted table (Shell method):                     *
'*                                                   *
'*   14   19   22   23   32   57   58   78   88   92 *
'*  104  128  143  143  145  157  163  183  195  215 *
'*  226  251  266  269  291  298  324  331  367  386 *
'*  389  398  398  405  408  417  426  447  451  472 *
'*  477  518  538  576  576  623  624  628  639  651 *
'*  652  671  672  674  676  680  711  712  731  735 *
'*  760  763  766  774  809  845  847  871  874  885 *
'*  886  888  903  925  936  938  942  948  952  991 *
'*                                                   *
'*****************************************************
defint i-n

dim  A(100)     'Table to be sorted

  cls
  N=80  'initialize size of table
  TMAXVALUE = 1000

  'initialize random generator
  RANDOMIZE TIMER

  'generate random table of numbers (from 0 to TMAXVALUE)
  for i=1 to N
    A(i)=TMAXVALUE*Rnd(1)
  next i

  print
  print " Table to be sorted:"
  gosub 2000 'call TWRIT(N,A)

  'call sorting subroutine
  gosub 1000 'call SHELL(N,A)

  print : print
  print " Sorted table (Shell method):"
  gosub 2000 'call TWRIT(N,A)

  print

END

'*****************************************************
'*  Sorts an array A of length N in ascending order  *
'*            by the Shell-Mezgar method             *
'* ------------------------------------------------- *
'* INPUTS:                                           *
'*	    N	  size of table ARR                  *
'*          A	  table to be sorted                 *
'* OUTPUT:                                           *
'*	    A     table sorted in ascending order    *
'*                                                   *
'* NOTE: The Shell method is a N^3/2 routine and can *
'*       be used for relatively large arrays.        *
'*****************************************************
1000 'Subroutine SHELL(N, A)

  ALN2I = 1.0/0.69314718
  HALF  = 0.5

  XN=N

  XLOGNB2 = INT(log(XN)*ALN2I+HALF)
  m=N
  for nn=1 to XLOGNB2
    m=m / 2 : k=N-m
    for j=1 to k
      i=j
10    l=i+m
      if A(l) < A(i) then
        t=A(i)
	A(i)=A(l)
	A(l)=t
	i=i-m
	if i >= 1 then goto 10
      end if
    next j
  next nn
return


'write table of size N to standard output
2000 'SUBROUTINE TWRIT(N,A)
  f$=" ####"
  print
  for i=1 to N
    print using F$; A(I);
    if INT(i/10)=i/10 then print
  next i
return

'end of file sort2.bas