Computers in Engineering WWW Site - Example 15.4

# Example 15.4

#### FORTRAN Version

!
PROGRAM P94
!
IMPLICIT NONE
INTEGER :: LIST(1000),COUNTS,NCOMP,NSWAP
INTEGER :: I,N
INTERFACE
SUBROUTINE SHAKE(LIST,N,COUNTS,NCOMP,NSWAP)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT):: LIST(:),N,COUNTS,NCOMP,NSWAP
SUBROUTINE BSORTR(LIST,L,M,K,COUNTS,NCOMP,NSWAP)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT) :: LIST(:),L,M,K,COUNTS,NCOMP,NSWAP
SUBROUTINE SWAP(LIST,K,L)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT):: LIST(:),K,L
END SUBROUTINE SWAP
END SUBROUTINE BSORTR
SUBROUTINE BSORTL(LIST,L,M,K,COUNTS,NCOMP,NSWAP)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT):: LIST(:),L,M,K,COUNTS,NCOMP,NSWAP COMMON /COUNTS/NCOMP,NSWAP
SUBROUTINE SWAP(LIST,K,L)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT):: LIST(:),K,L
END SUBROUTINE SWAP
END SUBROUTINE BSORTL
END SUBROUTINE SHAKE
END INTERFACE
!
!
PRINT *, 'This is Program>> P94 - Cocktail shaker sort'
!
! Tell program where data for READ * is coming from
OPEN(UNIT=5, FILE='P94.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 SHAKE(LIST,N,COUNTS,NCOMP,NSWAP)
!
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 P94
!
SUBROUTINE SHAKE(LIST,N,COUNTS,NCOMP,NSWAP)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT):: LIST(:),N,COUNTS,NCOMP,NSWAP
INTERGER :: LEFT,RIGHT,K
NCOMP=0
NSWAP=0
LEFT=1
RIGHT=N
L1: DO I=1,N
CALL BSORTR(LIST,LEFT,RIGHT,K,COUNTS,NCOMP,NSWAP)
IF(K == 0) RETURN
CALL BSORTL(LIST,LEFT,RIGHT,K)
IF(K == 0) RETURN
END DO L1
RETURN
END SUBROUTINE SHAKE
!
SUBROUTINE BSORTR(LIST,L,M,K,COUNTS,NCOMP,NSWAP)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT):: LIST(:),L,M,K,COUNTS,NCOMP,NSWAP
INTEGER :: I
!
! RIGHT BUBBLE SORT
!
M=M-1
K=0
L1: DO I=L,M
NCOMP=NCOMP+1
IF(LIST(I) > LIST(I+1))THEN
CALL SWAP(LIST,I,I+1)
NSWAP=NSWAP+1
K=I
ENDIF
END DO L1
M=K
RETURN
END SUBROUTINE BSORTR
!
SUBROUTINE BSORTL(LIST,L,M,K,COUNTS,NCOMP,NSWAP)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT):: LIST(:),L,M,K,COUNTS,NCOMP,NSWAP
INTEGER :: I
!
! LEFT BUBBLE SORT
!
L=L+1
K=0
L1: DO I=M,L,-1
NCOMP=NCOMP+1
IF(LIST(I) < LIST(I-1))THEN
CALL SWAP(LIST,I,I-1)
NSWAP=NSWAP+1
K=I
ENDIF
END DO L1
L=K
RETURN
END SUBROUTINE BSORTL
!
SUBROUTINE SWAP(LIST,K,L)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT):: LIST(:),K,L
INTEGER :: K
M=LIST(K)
LIST(K)=LIST(L)
LIST(L)=M
RETURN
END SUBROUTINE SWAP

#### C Version

/*
Cocktail shaker sort.
*/

#include <stdio.h>

typedef short listarray[1000]; /* Variable type declaration */
listarray list;            /* Global Variable Declaration */
short ncomp, nswap, n, i;

void swap(k, l)   /* Swap function declaration */
short *k, *l;
{
short temp;
temp = *k;
*k = *l;
*l = temp;
return(0);
}  /*  End of swap function  */

void bsortr(list, l, m, k)  /* bsortrsubroutine declaration */
short *list;
short *l, *m, *k;
{
/*  Right bubble sort  */

short i, FORLIM;
(*m)--;
*k = 0;
FORLIM = *m;
for (i = *l; i <= FORLIM; i++)
{
ncomp++;
if (list[i - 1] > list[i])
{
swap(&list[i - 1], &list[i]);   /* Call of swap function */
nswap++;
*k = i;
}
} /* End of for{} loop */
*m = *k;
} /* End of bsortr subroutine */

void bsortl(list, l, m, k)  /* bsortl function declaration */
short *list;
short *l, *m, *k;
{
/*  Left bubble sort  */

short i, FORLIM;
(*l)++;
*k = 0;
FORLIM = *l;
for (i = *m; i >= FORLIM; i--)
{
ncomp++;
if (list[i - 1] < list[i - 2])
{
swap(&list[i - 1], &list[i- 2]); /* Call of swap function */
nswap++;
*k = i;
}
} /* End of for{} loop */
*l = *k;
} /* End of bsortl subroutine */

void shake(list, n)  /* Shake subroutine declaration */

short *list;
short n;
{
short left, right, i, k;

ncomp = 0;
nswap = 0;
left = 1;
right = n;
i = 1;
do
{
bsortr(list, &left, &right,&k); /* Call of subroutine */
if (k != 0)
bsortl(list, &left, &right,&k); /* Call of subroutine */
i++;
} while (i <= n && k !=0); /* End of while{} loop */
} /*  End of Shake subroutine  */

main()
{
/*  Declaration Statements  */
short FORLIM;

clrscr();
printf("C94.C -> Cocktail Shaker Sort\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("Element %d : ",i);
scanf("%hd", &list[i- 1]);
}
printf("Press ""Enter""to continue...\n");
scanf("");
printf("\n");
printf("Before Sorting\n\n");
FORLIM = n;
for (i = 1; i <= FORLIM; i++) printf("%5d",list[i - 1]);
printf("\n\n");

/*  Sort with subroutines  */
shake(list, n);   /* Call of shake subroutine */

/* Print results */
printf("\nAfter Sorting\n\n");
FORLIM = 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 C94  */

/*
INPUT :
7
59
72
41
16
27
17
11

OUTPUT :
C94.C -> Cocktail Shaker Sort
Enter Number of Elements : 7
Enter elements (press enter between each 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= 21
Number of exchanges= 18
*/

#### Pascal Version

{\$G256}
{\$P512}
{\$D+}
PROGRAM p94 (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 bsortr (VAR list : listarray; VAR l, m, k : INTEGER);

{  Right bubble sort  }

VAR
i : INTEGER;
BEGIN
m := m - 1;
k := 0;
FOR i := l TO m DO
BEGIN
ncomp := ncomp + 1;
IF ( list[i] > list[i+1] ) THEN
BEGIN
swap (list[i], list[i+1]);
nswap := nswap + 1;
k := i
END
END;
m := k
END;

PROCEDURE bsortl (VAR list : listarray; VAR l, m, k : INTEGER);

{  Left bubble sort  }

VAR
i : INTEGER;
BEGIN
l := l + 1;
k := 0;
FOR i := m DOWNTO l DO
BEGIN
ncomp := ncomp + 1;
IF ( list[i] < list[i-1] ) THEN
BEGIN
swap (list[i], list[i-1]);
nswap := nswap + 1;
k := i
END
END;
l := k
END;

PROCEDURE shake (VAR list : listarray; n : INTEGER);
VAR
left, right, i, k : INTEGER;
BEGIN
ncomp := 0;
nswap := 0;
left := 1;
right := n;
i := 1;
REPEAT
bsortr (list, left, right, k);
IF (k <> 0) THEN
bsortl (list, left, right, k);
i := i + 1;
UNTIL ( (i > n) OR (k = 0) )
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  }

shake (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