Computers in Engineering WWW Site - Example 15.6

# 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
!
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 */
/*
```
INPUT :
```
7
59
72
41
16
27
17
11

```
OUTPUT :
```
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

*/
```

#### Pascal version

```{\$G256}
{\$P512}
{\$D+}
PROGRAM p95 (input, output);
TYPE
listarray = ARRAY[1..1000] OF INTEGER;
VAR
list : listarray;
ncomp, nswap, n, i : INTEGER;

PROCEDURE swap (VAR k, l : INTEGER);
VAR
temp : INTEGER;
BEGIN
temp := k;
k := l;
l := temp
END;

PROCEDURE shell (VAR list : listarray; n : INTEGER);
VAR
m, i, j : INTEGER;
done : BOOLEAN;
BEGIN
ncomp := 0;
nswap := 0;
m := n;
REPEAT
m := (m + 2) div 3;
FOR i := m+1 TO n DO
BEGIN
j := i;
done := false;
WHILE ((j >= m+1) AND (NOT done)) DO
BEGIN
ncomp := ncomp + 1;
IF ( list[j-m] < list[j] ) THEN
done := true
ELSE
BEGIN
swap (list[j], list[j-m]);
nswap := nswap + 1
END;
j := j - m
END
END;
UNTIL m <= 1
END;

BEGIN
FOR i := 1 TO n DO
writeln (^l);
writeln ('Before Sorting');
writeln;
FOR i := 1 TO n DO
write ( list[i] : 5);
writeln;
writeln;

{  Sort with subroutines  }

shell (list, n);

writeln;
writeln ('After Sorting');
writeln;
FOR i := 1 TO n DO
write ( list[i] : 5);
writeln;
writeln;
writeln ('Number of comparisons=', ncomp : 3);
writeln ('Number of exchanges=', nswap : 3);
writeln;
writeln
END.

```
DATA :
```7
59  72  41  16  27  17  11

```