!
! =====> Program - P97.F90
!
PROGRAM SrtDmo
! Program to demonstrate a number of simple
! sorting algorithms. N random integers are
! to be sorted in increasing order (from smallest
! to largest) in an array A.
PARAMETER (NMax = 1000)
INTEGER A(NMax), A0(NMax)
PRINT *, 'This is Program >> P97 = Sorting Demo'
!
! Tell program where data for READ * is coming from
OPEN(UNIT=5, FILE='P97.DAT') ! UNIT=5 is the default input
!
PRINT *, 'Number of elements to sort: '
READ *, N
Print *, N
Print *
!
CALL IniAry(A0, N)
CALL PrnAry(A0, N)
! Repeat for each sorting method
PRINT *, 'Bubble'
CALL CpyAry(A0, A, N)
CALL Bubble(A, N)
CALL PrnAry(A, N)
Print *
!
PRINT *, 'Insertion'
CALL CpyAry(A0, A, N)
CALL Insert(A, N)
CALL PrnAry(A, N)
Print *
!
PRINT *, 'Selection'
CALL CpyAry(A0, A, N)
CALL Select(A, N)
CALL PrnAry(A, N)
Print *
!
PRINT *, 'Shell'
CALL CpyAry(A0, A, N)
CALL Shell(A, N)
CALL PrnAry(A, N)
Print *
!
STOP
END
!
! SUPPORT ROUTINES
!
SUBROUTINE IniAry(A, N)
! Initializes N elements of array A to random
! non-negative integers.
PARAMETER (MaxInt = 32700)
INTEGER A(N), Seed
!
Seed = 31415
L1: DO I = 1, N
A(I) = ABS(MOD(INT(URand(Seed) * MaxInt) ,MaxInt))
END DO L1
RETURN
END
!
SUBROUTINE CpyAry(A0, A, N)
! Copy elements 1..N of array A0 to A.
!
INTEGER A0(N), A(N)
!
L1: DO I = 1, N
A(I) = A0(I)
END DO L1
RETURN
END
!
SUBROUTINE PrnAry(A, N)
! Prints the N elements of array A.
!
INTEGER A(N)
!
L1: DO I = 1, N
PRINT 101, I, A(I)
END DO L1
RETURN
101 FORMAT(1X, 'A(', I3, ') = ', I9)
END
!
SUBROUTINE Swap(I, J)
! Exchanges the integers I and J.
!
ITemp = I
I = J
J = ITemp
RETURN
END
!
! ALGORITHMS
!
SUBROUTINE Bubble(A, N)
INTEGER A(N)
!
! Make N-1 passes through the array.
! On pass i, "bubble" the next smallest element
! up from the end of the array to position i.
!
L1: DO I = 1, N-1
L2: DO J = N, I+1, -1
IF (A(J) < A(J-1)) THEN
CALL Swap(A(J), A(J-1))
ENDIF
END DO L2
END DO L1
RETURN
END
!
SUBROUTINE Insert(A, N)
INTEGER A(N)
!
! Make repeated passes through the array.
! On pass i, place the i'th element in its
! proper sorted position amongst the (sorted)
! A(1),...,A(i-1).
!
L1: DO I = 2, N
J = I
!
20 IF (A(J) >= A(J-1)) CYCLE
CALL Swap(A(J), A(J-1))
J = J-1
IF (J > 1) GO TO 20
END DO L1
!
RETURN
END
!
SUBROUTINE Select(A, N)
INTEGER A(N)
!
! Make N-1 passes through the array.
! On pass i, find the smallest element in
! A(i+1),...,A(N) and swap it with A(i),
! leaving the elements A(1),...,A(i) in their
! final, sorted order.
!
L1: DO I = 1, N-1
LowIdx = I
LowKey = A(I)
!
L2: DO J = I+1, N
IF (A(J) .LT. LowKey) THEN
LowKey = A(J)
LowIdx = J
ENDIF
END DO L2
!
CALL Swap(A(I), A(LowIdx))
END DO L1
!
RETURN
END
!
SUBROUTINE Shell(A, N)
INTEGER A(N)
!
! Incr is the number of positions separating
! elements of a particular tuple.
Incr = N / 2
!
! Make passes for Incr = N DIV 2, N DIV 4,
! N DIV 8,..., 1, and use Insertion Sort on
! elements separated by distances Incr
! on each pass.
!
DO WHILE (Incr > 0)
L1: DO I = Incr+1, N
J = I - Incr
!
15 IF (J <= 0) CYCLE
IF (A(J) > A(J+Incr)) THEN
CALL Swap(A(J), A(J+Incr))
J = J - Incr
ELSE
J = 0
ENDIF
!
GO TO 15
END DO L1
!
Incr = Incr / 2
END DO
!
RETURN
END
!
!
REAL FUNCTION URAND( XN )
INTEGER XN
!
! Uniform random number generator based on techniques described
! in "The Art of Computer Programming", Vol.2, Knuth.
!
! Xn+1 = a*Xn + c mod m
! where
! Xn is the seed supplied by the caller
! m = 2**31
! a = 2147437301
! c = 453816693
!
! 'a' satisfies the following:
!
! max( sm, m/10 ) < a < m - sm, where sm = square root of m
! a mod 8 = 5
!
! 'c' is computed as follows:
!
! c = idnint( 2d0**31 * ( .5d0 - dsqrt( 3d0 ) / 6d0 ) ) + 1
!
! Note: Integer arithmetic is automatically done modulo 2**31.
!
INTEGER A, M, C
DATA A/2147437301/
DATA M/80000000/
DATA C/453816693/
XN = A * XN + C
IF( XN < 0 ) XN = XN + M
URAND = XN / 2.0**31
END
DATA:
10
OUTPUT:
[FTN90 Version 1.12 Copyright (c)SALFORD SOFTWARE LTD 1992 & ]
[ (c)THE NUMERICAL ALGORITHMS GROUP 1991,1992]
NO ERRORS [FTN90]
Program entered
This is Program >> P97 = Sorting Demo
Number of elements to sort:
10
A( 1) = 17439
A( 2) = 4611
A( 3) = 15716
A( 4) = 12578
A( 5) = 19692
A( 6) = 3013
A( 7) = 144
A( 8) = 26656
A( 9) = 2094
A( 10) = 28624
Bubble
A( 1) = 144
A( 2) = 2094
A( 3) = 3013
A( 4) = 4611
A( 5) = 12578
A( 6) = 15716
A( 7) = 17439
A( 8) = 19692
A( 9) = 26656
A( 10) = 28624
Insertion
A( 1) = 144
A( 2) = 2094
A( 3) = 3013
A( 4) = 4611
A( 5) = 12578
A( 6) = 15716
A( 7) = 17439
A( 8) = 19692
A( 9) = 26656
A( 10) = 28624
Selection
A( 1) = 144
A( 2) = 2094
A( 3) = 3013
A( 4) = 4611
A( 5) = 12578
A( 6) = 15716
A( 7) = 17439
A( 8) = 19692
A( 9) = 26656
A( 10) = 28624
Shell
A( 1) = 144
A( 2) = 2094
A( 3) = 3013
A( 4) = 4611
A( 5) = 12578
A( 6) = 15716
A( 7) = 17439
A( 8) = 19692
A( 9) = 26656
A( 10) = 28624
Fortran-90 STOP
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#define true 1
#define false 0
/* This is a demonstration of various sorting techniques
An array is entered by the user, and the computer
uses all the algorithms discussed in the course to sort
it. This allows for comparison of the efficiency of
methods. */
/* ncomp and nswap are global variables, and each sorting function
will update them with the number of comparisons and swaps it did
when it was called. */
short ncomp, nswap;
void swap(k, l)
short *k, *l;
{
short temp;
temp = *k;
*k = *l;
*l = temp;
}
void sort1(list, n)
short *list;
short n;
{
short i, j;
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++;
}
}
}
}
void bsort1(list, n)
short *list;
short n;
{
short i, k;
ncomp = 0;
nswap = 0;
do {
k = 0;
for (i = 1; i < n; i++) {
ncomp++;
if (list[i - 1] > list[i]) {
swap(&list[i - 1], &list[i]);
nswap++;
k = 1;
}
}
} while (k != 0);
}
void bsort2(list, n)
short *list;
short n;
{
short last, k, i;
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]);
nswap++;
k = i;
}
}
last = k;
} while (k != 0);
}
void bsortr(list, l, m, k)
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]);
nswap++;
*k = i;
}
}
*m = *k;
}
void bsortl(list, l, m, k)
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]);
nswap++;
*k = i;
}
}
*l = *k;
}
void shake(list, n)
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);
if (k != 0)
bsortl(list, &left, &right, &k);
i++;
} while (i <= n && k != 0);
}
void shell(short list[], short n)
{
short temp, a, b, h;
nswap=0;
ncomp=0;
/* Outer loop varies the interval size */
for (h = n/2 ; h > 0; h = h/2){
/* This loop considers all sequences for a given interval size */
for (a = h; a < n; a = a + 1){
/* This loop sorts each individual sequence */
b = a-h;
while( b >= 0 ){
if( list[b] > list[b+h] ){
temp = list[b];
list[b]=list[b+h];
list[b+h]=temp;
nswap++;
}
b = b - h;
ncomp++;
}
}
}
}
void printinfo()
{
printf("number of comparisons = %5d\n", ncomp);
printf("number of exchanges = %5d\n", nswap);
}
int main(void)
{
short initial_list[1000];
short list[1000];
short n, i;
clrscr();
printf("This is a demonstration of sorting algorithms. \n\n");
printf(" You will be prompted to enter how large of an array you\n");
printf("to try sorting, and then enter the elements one by one.\n");
printf("Then the computer will sort them using all the algorithms\n");
printf("discussed under this section in the book, and will give\n");
printf("a comparison of how efficient each algorithm was.\n\n");
printf("Enter No. of Elements : ");
scanf("%hd", &n);
/* Now the computer must read in all the elements of the array.
It will store them in two arrays, called initial_list[] and
list[]. This is done so that after one technique sorts the
list, there is a copy of the original, unsorted list for the
next technique to work on, etc. */
for( i=0; i
Pascal version
{256}
{12}
{}
PROGRAM p96 (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 sort1 (VAR list : listarray; n : INTEGER);
VAR
i, j : INTEGER;
BEGIN
ncomp := 0;
nswap := 0;
FOR i := 1 TO n-1 DO
FOR j := i+1 TO n DO
BEGIN
ncomp := ncomp + 1;
IF (list[i] > list[j]) THEN
BEGIN
swap (list[i], list[j]);
nswap := nswap + 1
END
END
END;
PROCEDURE bsort1 (VAR list : listarray; n : INTEGER);
VAR
i, k : INTEGER;
BEGIN
ncomp := 0;
nswap := 0;
REPEAT
k := 0;
FOR i := 1 TO n-1 DO
BEGIN
ncomp := ncomp + 1;
IF ( list[i] > list[i+1] ) THEN
BEGIN
swap (list[i], list[i+1]);
nswap := nswap + 1;
k := 1
END
END
UNTIL k = 0
END;
PROCEDURE bsort2 (VAR list : listarray; n : INTEGER);
VAR
last, k, i : INTEGER;
BEGIN
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;
last := k
UNTIL k = 0
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;
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;
PROCEDURE printinfo;
BEGIN
writeln ( 'number of comparisons = ', ncomp:5 );
writeln ( 'number of exchanges = ', nswap:5 );
writeln;
writeln
END;
PROCEDURE gen ( VAR list : listarray ;
n : INTEGER );
VAR
i : INTEGER;
BEGIN
{
Random (x) returns a random integer between 0 and x not inclusive
Randomize resets the random generator
}
randomize;
FOR i := 1 TO n DO
list[i] := random ( n + 1 )
END;
BEGIN
WHILE ( NOT eof ) DO
BEGIN
readln ( n );
gen ( list, n );
sort1 ( list, n );
writeln ( 'Sort1 : ' );
printinfo;
gen ( list, n );
bsort1 ( list, n );
writeln ( 'Bsort1 : ');
printinfo;
gen ( list, n );
bsort2 (list, n );
writeln ( 'Bsort2 : ');
printinfo;
gen ( list, n );
shake ( list, n );
writeln ( 'Shake : ' );
printinfo;
gen ( list, n );
shell ( list, n );
writeln ( 'Shell : ' );
printinfo
END
END.
DATA:
10
100
Last modified: 08/07/97