! 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 ! 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 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
/* 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 11OUTPUT :
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 */
{$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 readln (n); FOR i := 1 TO n DO read (list[i]); readln; 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
Last modified: 08/07/97