!
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 BSORT2
DATA:
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