! 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
/* 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 11OUTPUT :
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 */
{$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 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 } 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
Last modified: 08/07/97