covert@ihuxq.UUCP (covert) (06/04/84)
< to the line eating wombat >
I recently bought a book written by Jack Purdum, Tim Leslie, and
Alan Stegemoller titled "C Programmer's Library". This file contains a
version of the bubble sort function in their book with conforms to the
UNIX standard library. This version of bsort() is used in the same manner
as the ATT UNIX System V Release 2.0 version of qsort(3C). I have also
included a test program which can be used to test the bsort function,
or with minor changes the qsort function.
Remember to strip out the trailing lines of this message.
# to unbundle, csh this file
echo readme
cat >readme <<'End of readme'
readme
This documents the bubble sort function. The bubble sort function is
based upon the bubble sort function described in the book "C Programmer's
Library" written by Jack J. Purdum, Timothy C. Leslie, and Alan L.
Stegemoller; published by Que Corporation Indianapolis, Indiana 1984.
The function as written conforms in usage with the qsort function
available in the ATT UNIX System V Release 2.0 library.
Compile the file bsort.c:
cc -O -c bsort.c
Compile the file bsorttst.c
cc -O -o bsorttst bsorttst.c bsort.o
bsort.3c is the manual page for the bsort function.
The reason that this function is different from the function in the
book is that the function required the data table to be global, and the
swap function to be written for each type of data to be sorted. This version
of bsort allows any simple, or aggregate, data type to be sorted. The user
needs to write only the compare function used by bsort. The file bsorttst.c
contains examples of three uses of the bsort function. One uses bsort to sort
integers, one for sorting doubles, and one for sorting a structure using the
second field as the key. This same program can be used to test the qsort
function simply by changing all calls to bsort() to calls to qsort().
'End of readme'
echo bsorttst.c
cat >bsorttst.c <<'End of bsorttst.c'
/* EMACS_MODES: tabstop=4, c, !save, !fill, !lnumb */
/* bubblesort.c --A bubble sort routine. This is the based upon the
* bubble sort routine in the book "C Programmer's Library".
* I have rewritten it to confirm to the format of the qsort
* function in the UNIX System V Release 2.0 standard library.
*
* author: r.e.covert ihnp4!ihuxq!covert
*
* date: 6/4/84
*
* Original Source: 'C' Programmer's Library by Jack J. Purdum,
* Timothy C. Leslie, Alan L. Stegemoller
* Published by Que Corporation Indianapolis Indiana 1984
*
* Usage:
* bsort(3)
* void bsort(base, nel, sel, cmpr)
* char *base;
* unsigned int nel;
* unsigned int sel;
* int (*cmpr)();
*
*/
/*************************************************************************
*
* This program performs a bubble sort on 'n' records. It is independent
* of the record and key. This independence is possible because pointers
* to a key-comparison and record-swapping function are passed to the sort.
* The function convention is
*
* bsort((char *) base, nel, sel, compar)
*
* Where
*
* base points to the element at the base of the table. base is of
* type pointer-to-element and is cast to pointer-to-char.
*
* nel is the number of elements to sort.
*
* sel is the size of each element.
*
* compar is a pointer to a function that will compare two record keys
* and return an integer representing the logical relationship of
* the keys. Returns:
*
* < 0 If key[i] < key[j] (ascending) or
* key[i] > key[j] (descending)
* = 0 If key[i] == key[j]
* > 0 If key[i] > key[j] (ascending) or
* key[i] < key[j] (descending)
*
* compar is called with two paramters that are indices to
* records, with the record being 0 and the last record being n-1.
*
************************************************************************/
/*************************************************************************
*
* This proram illustrates the use of pointers to functions.
* In this program the pointers to functions are used to allow
* the sort algorithm to function independently of the date record.
*
************************************************************************/
#ifndef void
#define void int
#endif
struct form1 {
int a;
int b;
float c;
char d;
}
main()
{
struct form1 *p;
static struct form1 data1[] = {
{ 73, 987, 123.456, 'a' },
{ 54, 123, 876.77, 'b' },
{ 123, 456, 34.0009, 'c' },
{ 112, 023, 435.700, 'd' },
{ 8, 1, 1.12, 'e'}
};
static int int_data[] = {
12, 100, -9, -999, 1211, 12, 13, 0, 999, -1, 1 };
static double dbl_data[] = {
12.0, 100.0, -9.0, -999.0, 1211.0, 12.0, 13.0, 0.0, 999.0, -1.0, 1.0};
int nel, int_nel, dbl_nel, i , j;
int int_compar(), dbl_compar(), struct_cmpr();
extern int bsort();
int_nel = sizeof(int_data)/sizeof(int_data[0]);
printf("Integer table before sorting.\n");
for (i = 0; i < int_nel; ++i)
printf(" %d", int_data[i]);
printf("\nInteger table after sorting.\n");
bsort( (char *)int_data, int_nel, sizeof(int_data[0]), int_compar);
for (i = 0; i < int_nel; ++i)
printf(" %d", int_data[i]);
printf("\n");
printf("Double Data table before sorting.\n");
dbl_nel = sizeof(dbl_data)/sizeof(dbl_data[0]);
for (i = 0; i < dbl_nel; ++i)
printf(" %9.4f", dbl_data[i]);
printf("\nDouble Data table after sorting.\n");
bsort((char *) dbl_data, dbl_nel, sizeof(dbl_data[0]), dbl_compar);
for (i = 0; i < dbl_nel; ++i)
printf(" %9.4f", dbl_data[i]);
printf("\n");
printf("\n\n\n");
nel = sizeof(data1)/sizeof(data1[0]);
printf("Complex structure before sorting.\n");
for(p = data1, i = 0; i < nel; i++, p++)
printf("%5d %5d %9.4f %c\n", p->a, p->b, p->c, p->d);
bsort(data1, nel, sizeof(data1[0]), struct_cmpr);
printf("\n\n\n");
printf("Complex structure after sorting.\n");
for(p = data1, i = 0; i < nel; i++, p++)
printf("%5d %5d %9.4f %c\n", p->a, p->b, p->c, p->d);
}
int
int_compar(i, j) /* integer comparison function */
int *i, *j; /* pointers to integer data */
{
if (*i < *j )
return(-1);
else if (*i == *j)
return(0);
else
return(1);
}
int
dbl_compar(i, j) /* double comparison function */
double *i,*j; /* pointers to double data */
{
if (*i < *j )
return(-1);
else if (*i == *j)
return(0);
else
return(1);
}
int
struct_cmpr(p1, p2)
struct form1 *p1, *p2;
{
int ret = 0;
if (p1->b < p2->b)
ret = -1;
else if ( p1->b > p2->b)
ret = 1;
return(ret);
}
'End of bsorttst.c'
echo bsort.c
cat >bsort.c <<'End of bsort.c'
/* EMACS_MODES: tabstop=4, c, !save, !fill, !lnumb */
/* bubblesort.c --A bubble sort routine. This is the based upon the
* bubble sort routine in the book "C Programmer's Library".
* I have rewritten it to confirm to the format of the qsort
* function in the UNIX System V Release 2.0 standard library.
*
* author: r.e.covert
*
* date: 6/4/84
*
* Original Source: 'C' Programmer's Library by Jack J. Purdum,
* Timothy C. Leslie, Alan L. Stegemoller
* Published by Que Corporation Indianapolis Indiana 1984
*
* Usage:
* bsort(3)
* void bsort(base, nel, sel, cmpr)
* char *base;
* unsigned int nel;
* unsigned int sel;
* int (*cmpr)();
*
*/
/************************************************************************
*
* Bubble Sort
* As described by Knuth, p.107
*
************************************************************************/
/*************************************************************************
*
* This program performs a bubble sort on 'n' records. It is independent
* of the record and key. This independence is possible because pointers
* to a key-comparison and record-swapping function are passed to the sort.
* The function convention is
*
* bsort((char *) base, nel, sel, compar)
*
* Where
*
* base points to the element at the base of the table. base is of
* type pointer-to-element and is cast to pointer-to-char.
*
* nel is the number of elements to sort.
*
* sel is the size of each element.
*
* compar is a pointer to a function that will compare two record keys
* and return an integer representing the logical relationship of
* the keys. Returns:
*
* < 0 If key[i] < key[j] (ascending) or
* key[i] > key[j] (descending)
* = 0 If key[i] == key[j]
* > 0 If key[i] > key[j] (ascending) or
* key[i] < key[j] (descending)
*
* compar is called with two paramters that are indices to
* records, with the record being 0 and the last record being n-1.
*
************************************************************************/
/*************************************************************************
*
* This proram illustrates the use of pointers to functions.
* In this program the pointers to functions are used to allow
* the sort algorithm to function independently of the date record.
*
************************************************************************/
#ifndef void
#define void int
#endif
/* Bubble Sort Functions */
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
void
bsort(base, nel, sel, cmpr) /* bubble sort function */
char *base; /* pointer to base of data table */
unsigned nel; /* Number of elements in the data table */
unsigned sel; /* The size of each element in the data table */
int (*cmpr)(); /* A pointer to comparison function */
{
unsigned j;
int unsorted = FALSE;
char *ptr1, *ptr2; /* pointers to elements in data table */
void bsexch(); /* exchange function for bsort() */
int ret;
/* Psuedo-code :
while not sorted {
Assume table is sorted (set not sorted flag to false);
set first pointer to bottom of table;
set second pointer to first data item above first pointer;
Verify that each item in the table is sorted by repeatedly
searching the table for two adjacent items that are NOT
sorted. If two adjacent items are not sorted then exchange them,
set the not sorted flag TRUE, and continue searching the data table.
If the not sorted flag is true when you reach the end of the table
then start set the not sorted flag false, reset the data pointers to
the bottom of the data table, and start searching the table again.
Repeat this process until a complete pass through the table yields
all items in sorted order.
}
*/
do {
unsorted = FALSE; /* break loop if unsorted == false */
ptr1 = base; /* set pointers to base of table */
ptr2 = base + sel; /* & to base + 1 of table */
for(j = 0; j < nel-1; ++j) { /* do not go past the end of the table */
ret = (*cmpr)(ptr1, ptr2); /* perform the comparison */
if ( ret > 0) { /* compare 2 pointers */
bsexch(ptr1, ptr2, sel); /* exchange 2 pointers */
unsorted = TRUE; /* continue to next pair of elements */
}
ptr1 += sel; ptr2 += sel;/* increment both pointers */
}
} while(unsorted); /* loop until entire table is sorted (nel*nel times) */
}
void
bsexch(i, j, n)
char *i, *j;
int n;
{
register char *ri, *rj, c;
ri = i;
rj = j;
do {
c = *ri;
*ri++ = *rj;
*rj++ = c;
} while (--n);
}
/**************************** end of bsort functions ********************/
'End of bsort.c'
echo bsort.3
cat >bsort.3 <<'End of bsort.3'
.TH BSORT 3 "UNSUPPORTED"
.SH NAME
bsort \- bubble sort
.SH SYNOPSIS
.B "void bsort ((char \(**) base, nel, sizeof (\(**base), compar)"
.br
.B unsigned int nel;
.br
.B int (\(**compar)( );
.SH DESCRIPTION
.I Bsort\^
is an implementation
of the bubble-sort algorithm.
It sorts a table of data in place.
.PP
.I Base\^
points to the element at the base of the table.
.I Nel\^
is the number of elements in the table.
.I Compar\^
is the name of the comparison function,
which is called with two arguments that point
to the elements being compared.
The function must return
an integer less than, equal to, or greater than zero
according as the first argument is to be considered
less than, equal to, or greater than the second.
.SH NOTES
The pointer to the base of the table should be
of type pointer-to-element,
and cast to type pointer-to-character.
.br
The comparison function need not compare every byte,
so arbitrary data may be contained in the elements in addition to the values
being compared.
.br
Although declared as type pointer-to-character,
the value returned should be cast into type pointer-to-element.
.SH SEE ALSO
sort(1), qsort(3C), bsearch(3C), lsearch(3C), string(3C).
'End of bsort.3'
--
Richard Covert
AT&T Bell Laboratories
...ihnp4!ihuxq!covert
(312) 979-7488
geoff@callan.UUCP (06/09/84)
Jack Purdum is rapidly getting a reputation as an idiot with me. I thought that by now *EVERYBODY* knew that the bubble sort is for cretins. If you want a quick simple sort, write a "selection sort": search 0 thru n for the largest item and swap it with the item in slot n; repeat with n=n-1 until done. This is exactly the effect that the bubble sort achieves (think about it for a while if you aren't sure), but without all the unnecessary exchanges. Moral: Don't waste your effort optimizing the wrong solution to the problem. Geoff Kuenning Callan Data Systems ...!ihnp4!wlbr!callan!geoff
mas@ecsvax.UUCP (06/11/84)
Wirth states, " ... in fact, the Bubblesort has hardly anything to recommend it except its catchy name. " page 68 of Algorithms + Data Structures = Programs . ...decvax!mcnc!ecsvax!mas
gsp@ulysses.UUCP (Gary Perlman) (06/12/84)
> Jack Purdum is rapidly getting a reputation as an idiot with me. I thought > that by now *EVERYBODY* knew that the bubble sort is for cretins. If you > want a quick simple sort, write a "selection sort": search 0 thru n for the > largest item and swap it with the item in slot n; repeat with n=n-1 until > done. This is exactly the effect that the bubble sort achieves (think about > it for a while if you aren't sure), but without all the unnecessary exchanges. > Moral: Don't waste your effort optimizing the wrong solution to the problem. > Geoff Kuenning > Callan Data Systems > ...!ihnp4!wlbr!callan!geoff It is true that bubble sort is about as bad an algorithm as can be found. Floor sort, used by me when I once dropped my FORTAN deck, is a bit worse. Still, bubble sort is useful as a teaching tool, and its impracticality makes it unlikely that teachers can find implementations of it in C. I have trouble finding serious fault with anyone generous enough to post their software to net.sources. I realized that I was free to ignore it. So while I can't cheer for the posting of some code that people should not use for efficiency's sake, I find personal attacks in very poor taste. For another non-optimal sorting routine, see the standard C text, The C Programming Language (Prentice Hall) for a shell sort routine. For small arrays, it gives remarkably good results for such a small procedure. Gary Perlman BTL MH 5D-105 (201) 582-3624 ulysses!gsp
mickey@proper.UUCP (06/13/84)
>> Wirth states, " ... in fact, the Bubblesort has hardly anything to >> recommend it except its catchy name. " >> page 68 of Algorithms + Data Structures = Programs . >> >> ...decvax!mcnc!ecsvax!mas >> That statement actually came from Knuth. See page 111 of Volume 3 from "The Art of Computer Programming". I read somewhere, though i am sorry i can't give a reference, that bubble sort is quite efficient for N <= 10 (where N is the number of records to be sorted). M. Thompson
ags@pucc-i (06/17/84)
> I read somewhere, though i am sorry i can't give a reference, that > bubble sort is quite efficient for N <= 10 (where N is the number of > records to be sorted). You could also say that BASIC is quite efficient for N <= 10 (where N is the number of lines in the program). -- Dave Seaman "My hovercraft is full of eels." ..!pur-ee!pucc-i:ags
nessus@mit-eddie.UUCP (Doug Alan) (06/18/84)
> From: mickey@proper.UUCP > I read somewhere, though i am sorry i can't give a reference, > that bubble sort is quite efficient for N <= 10 (where N is the > number of records to be sorted). The bubble sort is efficient for N <= 10, but the straight insertion sort, which is easier to do, is more efficient. -- -Doug Alan mit-eddie!nessus Nessus@MIT-MC "What does 'I' mean"?