PROGRAM P95 IMPLICIT NONE INTEGER :: LIST(1000),NCOMP,NSWAP,N,I INTERFACE SUBROUTINE SELECT(LIST,N,NCOMP,NSWAP) IMPLICIT NONE INTEGER,INTENT(IN) :: N INTEGER,INTENT(IN OUT) :: LIST(:) INTEGER,INTENT(OUT) :: NCOMP,NSWAP END SUBROUTINE SELECT END INTERFACE ! ! PRINT *, 'This is Program >> P95 - Selection sort' ! ! Tell program where data for READ * is coming from OPEN(UNIT=5, FILE='P95.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 SELECT(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 P95 ! SUBROUTINE SELECT(LIST,N,NCOMP,NSWAP) ! IMPLICIT NONE INTEGER,INTENT(IN) :: N INTEGER,INTENT(IN OUT) :: LIST(:) INTEGER,INTENT(OUT):: NCOMP,NSWAP INTEGER :: SMALL,I,J,K,TEMP PRINT 18, 18 FORMAT(' SORTING'/) NCOMP=0 NSWAP=0 L1: DO I=1,N-1 SMALL=LIST(I) K=I L2: DO J=I+1,N NCOMP=NCOMP+1 IF(LIST(J)<SMALL) THEN K=J SMALL=LIST(J) END IF END DO L2 TEMP=LIST(I) LIST(I)=LIST(K) LIST(K)=TEMP NSWAP=NSWAP+1 PRINT 16, (LIST(K),K=1,N) 16 FORMAT(20I5) END DO L1 RETURN END SUBROUTINE SELECT !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 = 30164 Kb | +--------------------------------------------------+ This is Program >> P95 - Selection sort BEFORE SORTING 59 72 41 16 27 17 11 SORTING 11 72 41 16 27 17 59 11 16 41 72 27 17 59 11 16 17 72 27 41 59 11 16 17 27 72 41 59 11 16 17 27 41 72 59 11 16 17 27 41 59 72 AFTER SORTING 11 16 17 27 41 59 72 NUMBER OF COMPARISONS= 21 NUMBER OF EXCHANGES= 6
#include <stdio.h> /* Program C91.C - Selection Sort */ typedef short listarray[1000]; listarray list; short ncomp, nswap, n, i; void swap(k, l) short *k, *l; { short temp; temp = *k; *k = *l; *l = temp; return(0); } void sort1(list, n) short *list; short n; { short i, j, k; printf("Sorting\n\n"); ncomp = 0; nswap = 0; for (i = 0; i <= n - 2; i++) { for (j = i + 1; j < n; j++) { ncomp++; if (list[i] > list[j]) { swap(&list[i], &list[j]); nswap++; } } for (k = 0; k < n; k++) printf("%5d", list[k]); putchar('\n'); } } int main(void) { short FORLIM; printf("C91.C > demonstration of Selection Sort\n"); printf("Enter No. of Elements : "); scanf("%hd", &n); FORLIM = 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 */ sort1(list, n); 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. */ #include <stdio.h> /* Program C91.C - Selection Sort */ typedef short listarray[1000]; listarray list; short ncomp, nswap, n, i; void swap(k, l) short *k, *l; { short temp; temp = *k; *k = *l; *l = temp; return(0); } void sort1(list, n) short *list; short n; { short i, j, k; printf("Sorting\n\n"); ncomp = 0; nswap = 0; for (i = 0; i <= n - 2; i++) { for (j = i + 1; j < n; j++) { ncomp++; if (list[i] > list[j]) { swap(&list[i], &list[j]); nswap++; } } for (k = 0; k < n; k++) printf("%5d", list[k]); putchar('\n'); } } int main(void) { short FORLIM; printf("C91.C > demonstration of Selection Sort\n"); printf("Enter No. of Elements : "); scanf("%hd", &n); FORLIM = 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 */ sort1(list, n); 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. */
{$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