Example 15.6

FORTRAN Version

!
      PROGRAM P96
!
      IMPLICIT NONE
      INTEGER :: LIST(1000),COUNTS,NCOMP,NSWAP
      INTEGER :: I,N
      INTERFACE 
        SUBROUTINE SHELL(LIST,N,COUNTS,NCOMP,NSWAP)
          IMPLICIT NONE
          INTEGER ,INTENT(IN OUT) :: LIST(:),COUNTS,NCOMP,NSWAP,N
          SUBROUTINE SWAP(LIST,K,L)
            IMPLICIT NONE
            INTEGER ,INTENT(IN OUT) :: LIST(:),K,L
          END SUBROUTINE SWAP 
        END SUBROUTINE SHELL
      END INTERFACE
!
!
      PRINT *, 'This is Program >>P96  - Shell sort'
!
!     Tell program where data for  READ*  is coming from
      OPEN(UNIT=5, FILE='P96.DAT') 
! UNIT=5 is the default input
!
      READ * ,N
      READ * ,(LIST(I),I=1,N)
      PRINT 17
  17  FORMAT(/'BEFORE SORTING'/)
      PRINT 16,(LIST(I),I=1,N)
      PRINT * ,' '
!
!     SORT WITH SUBROUTINES
!
      CALL SHELL(LIST,N)
!
      PRINT 14
  14  FORMAT(/'AFTER SORTING'/)
      PRINT 16,(LIST(I),I=1,N)
  16  FORMAT(20I5)
      PRINT 27,NCOMP,NSWAP
  27  FORMAT('NUMBER OF COMPARISONS=',I3/&'NUMBER OF EXCHANGES=',I3//)
      STOP
      END PROGRAM P96
!
      SUBROUTINE SHELL(LIST,N,COUNTS,NCOMP,NSWAP)
      IMPLICIT NONE
      INTEGER ,INTENT(IN OUT) :: LIST(:),COUNTS,NCOMP,NSWAP,N
      INTEGER :: M,I,J
      NCOMP=0
      NSWAP=0
      M=N
L1:   DO WHILE (M > 1)
         M=(M+2)/3
L2:      DO I=M+1,N
L3:         DO J=I,M+1,-M
               NCOMP=NCOMP+1
               IF(LIST(J-M) < LIST(J))EXIT
               CALL SWAP(LIST,J,J-M)
               NSWAP=NSWAP+1
            END DO L3
         END DO L2
      END DO L1
      RETURN
      END SUBROUTINE SHELL
!
      
      SUBROUTINE SWAP(LIST,K,L)
      IMPLICIT NONE
      INTEGER ,INTENT(IN OUT) :: LIST(:),K,L
      INTEGER :: M
      M=LIST(K)
      LIST(K)=LIST(L)
      LIST(L)=M
      END SUROUTINE SWAP

C Version

/*
  Shell Sort.
*/

#include <stdio.h>

#define true 1     /* Constant declaration*/
#define false 0

typedef int listarray[1000]; /* Variable type declaration */

listarray list;           /* Global variable declaration */

int ncomp, nswap, n, i;

void swap(int *k, int *l)  /* Swap function declaration */
{
  int temp;

  temp = *k;
  *k = *l;
  *l = temp;
}  /* End swap function */

void shell(int *list, int n)   /* Shell subroutine declaration */
{
  int m, i, j;
  int done;

  ncomp = 0;
  nswap = 0;
  m = n;
  do
  {
    m = (m + 2) / 3;
    for (i = m + 1; i <= n; i++)
    {
      j = i;
      done = false;
      while (j > m && !done)
{
     ncomp++;
     if (list[j - m - 1] < list[j- 1]) done = true;
     else
     {
     swap(&list[j - 1], &list[j- m - 1]); /* Call of Swap function */
     nswap++;
     }
     j -= m;
      }
    }
  }while(m > 1);
}

main()
{
  /*  Declaration Statements  */
  int n;
  int list[100];
  int FORLIM;

  clrscr();
  printf("C95.C -> Shell sort program\n");

  /*  Assignment Statements  */
  printf("Enter the number of elements:");
  scanf("%hd", &n);
  FORLIM = n;

  printf("Enter elements (press""enter"" between each entry)\n");

  for (i = 1; i <= FORLIM; i++)
  {
    printf("Enter element %d: ",i);
    scanf("%hd", &list[i- 1]);
  }
  printf("\n\nBefore Sorting\n\n");

  /* Print out initial array */

 for (i = 1; i <= FORLIM; i++) printf("%5d",list[i - 1]);
  printf("\n\n");

  /*  Sort with subroutines  */

  shell(list, n);  /* Call of shell subroutine */

  /* Print out sorted array */

  printf("\nAfter Sorting\n\n");

  for (i = 1; i <= FORLIM; i++) printf("%5d",list[i - 1]);

  printf("\n\nNumber of comparisons=%3d\n",ncomp);

  printf("Number of exchanges=%3d\n\n\n",nswap);

  return(0);
}
/*  End of main Program C95 */
/*

7
59
72
41
16
27
17
11

C95.C -> Shell sort program
Enter Number of Elements : 7
Enter elements (press enter betweeneach entry)
Element 1 : 59
Element 2 : 72
Element 3 : 41
Element 4 : 16
Element 5 : 27
Element 6 : 17
Element 7 : 11
Press Enter to continue...

Before Sorting
   59   72   41   16   27   17   11


After Sorting
   11   16   17   27   41   59   72

Number of comparisons= 16
Number of exchanges= 10

*/