! PROGRAM P93 ! IMPLICIT NONE INTEGER :: LIST(1000) INTEGER :: N,I INTEGER :: NCOMP,NSWAP ! INTERFACE SUBROUTINE BSORT2(LIST,N,NCOMP,NSWAP) IMPLICIT NONE INTEGER, INTENT(IN OUT) :: LIST(:) INTEGER, INTENT(IN OUT) :: NSWAP INTEGER, INTENT(IN OUT) :: NCOMP INTEGER, INTENT(IN OUT) :: N END SUBROUTINE BSORT2 END INTERFACE ! ! PRINT *, 'This is Program >> P93 - Better Bubble sort' ! ! 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 BSORT2(LIST,N,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 P93 ! SUBROUTINE BSORT2(LIST,N,NCOMP,NSWAP) IMPLICIT NONE INTEGER :: K,I,LAST,KK,TEMP1 INTEGER, INTENT(IN OUT) :: LIST(:) INTEGER, INTENT(IN OUT) :: NSWAP INTEGER, INTENT(IN OUT) :: NCOMP INTEGER, INTENT(IN OUT) :: N PRINT 23 23 FORMAT(/' SORTING'/) NCOMP=0 NSWAP=0 LAST=N-1 L1: DO K=0 L2: DO I=1,LAST NCOMP=NCOMP+1 IF(LIST(I) > LIST(I+1))THEN TEMP1=LIST(I) LIST(I)=LIST(I+1) LIST(I+1)=TEMP1 NSWAP=NSWAP+1 K=I ! Remember swap location END IF END DO L2 PRINT 16,(LIST(KK),KK=1,N) 16 FORMAT(20I5) LAST=K IF(K == 0) EXIT ! No more swaps END DO L1 RETURN END SUBROUTINE BSORT2DATA:
7 59 72 41 16 27 17 11OUTPUT:
+--------------------------------------------------+ | 32-bit Power for Lahey Computer Systems | | Phar Lap's 386|DOS-Extender(tm) Version 7.0 | | Copyright (C) 1986-94 Phar Lap Software, Inc. | | Available Memory = 14880 Kb | +--------------------------------------------------+ This is Program >> P93 - Better Bubble sort BEFORE SORTING 59 72 41 16 27 17 11 SORTING 59 41 16 27 17 11 72 41 16 27 17 11 59 72 16 27 17 11 41 59 72 16 17 11 27 41 59 72 16 11 17 27 41 59 72 11 16 17 27 41 59 72 11 16 17 27 41 59 72 AFTER SORTING 11 16 17 27 41 59 72 NUMBER OF COMPARISONS= 27 NUMBER OF EXCHANGES= 18
/* Improved version of the bubble 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; } /* End of swap function */ void bsort2(list, n) /* bsort2 subroutine declaration */ short *list; short n; { short last, k, i, kk; printf("Sorting\n"); ncomp = 0; nswap = 0; last = n - 1; do { k = 0; for (i = 1; i <= last; 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 */ for (kk = 0; kk < n; kk++) printf("%5d", list[kk]); putchar('\n'); last = k; } while (k != 0); } /* End of bsort2 subroutine */ main() { /* Declaration Statement */ short FORLIM; clrscr(); printf("C93.C -> Improved version of the bubble sort\n"); /* Assignment Statements */ printf("Enter the number of Elements : "); scanf("%hd", &n); FORLIM = n; for (i = 1; i <= FORLIM; i++) { printf("Element %d : ",i); /* Read element from keyboard entry */ 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 */ bsort2(list, n); /* Call of subroutine */ 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 C93 */ /*INPUT :
7 59 72 41 16 27 17 11OUTPUT :
C93.C -> Improved version of the bubble sort Enter the number of Elements : 7 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 Sorting 59 41 16 27 17 11 72 41 16 27 17 11 59 72 16 27 17 11 41 59 72 16 17 11 27 41 59 72 16 11 17 27 41 59 72 11 16 17 27 41 59 72 11 16 17 27 41 59 72 After Sorting 11 16 17 27 41 59 72 Number of comparisons= 27 Number of exchanges= 18 */
{$G256} {$P512} {$D+} PROGRAM p93 (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 bsort2 (VAR list : listarray; n : INTEGER); VAR last, k, i, kk : INTEGER; BEGIN write ('Sorting'); writeln; ncomp := 0; nswap := 0; last := n - 1; REPEAT k := 0; FOR i := 1 TO last 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; FOR kk := 1 TO n DO write ( list[kk] : 5); writeln; last := k; UNTIL 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 } bsort2 (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