How to write a sorting program that will sort everything?

[Blair P. Houghton]

In article <1991Mar22.005700.17663 at minyos.xx.rmit.oz.au> rcoahk at chudich.co.rmit.oz (Alvaro Hui Kau) writes:
>Hi,
>	Recently I came into the problem of writing
>	a sorting program that needs to handle any
>	type of input.

It can't be done.  You can always define a type of input
for which "sorting" isn't defined.  For example, strings in
unix are usually sorted according to ASCII collating
sequence, so that A-Z appear before a-z; this is because,
represented as integers in the machine, this is the actual
order in which they appear.  The sort(1) program needs a
flag (usually `-f') to tell it when to sort according to
linguistic rules rather than arbitrary computer rules.

What you seem to want, however, is a program to sort any
of the basic types available in C.  This is easy.  Define
a union in which there is a tag for every one of the type
specifiers you might use:

	union c_basic_types {
	    float f;
	    double d;
	    int i;
	    ...
	};

and a set of constants you can use to flag the function:

#define SORT_FLOAT	1
#define SORT_DOUBLE	2
#define SORT_INT	3
...

and implement a switch to use the proper union tag when
the flag is passed

union c_basic_types
max( union c_basic_types x, union c_basic_types y, int sort_type )
{
    switch ( sort_type ) {
	case SORT_FLOAT:
	    return ( x.f > y.f ) ? x : y ;
	    break;
	case SORT_DOUBLE:
	    return ( x.d > y.d ) ? x : y ;
	    break;
	case SORT_INT:
	    return ( x.i > y.i ) ? x : y ;
	    break;
	...
	default:
	    /* some sort of error message for a type that isn't recognized */
	    exit(-1);
	    break;
    }
}

This is just the max() function; with an array or list of
unions you can implement a full sort.  Look into the
library function qsort(3). You can use this max function in
qsort if you modify it to use a global variable to pass the
sort_type and you have it return 1 when the value in x is
larger and 0 when the value in y is larger

main.c:
    extern int max( union c_basic_types x, c_basic_types y ); /* prototype */
    int sort_type;

    main()
    {
	union c_basic_types a[SIZE];
	extern int sort_type;

	.../* code to fill the array */...

	.../* code to set sort_type to some type */...

	qsort( a, SIZE, sizeof(a[0]), max );

	.../* code to use the sorted array */...
    }

max.c:
    int max( union c_basic_types x, c_basic_types y )
    {
	extern int sort_type;

	switch ( sort_type ) {
	    case SORT_FLOAT:
		return ( x.f > y.f );
		break;
	    case SORT_DOUBLE:
		return ( x.d > y.d );
		break;
	    case SORT_INT:
		return ( x.i > y.i );
		break;
	    ...
	    default:
		/* unrecognized type; print error message and die */
		fputs("Mickle foo and yer mama, too!",stderr);
		exit(-1);
		break;
	}
    }

The basic point here is you can't sort a type for which
you haven't defined the ordering method.  This is the
reason qsort(3) requires such a strange setup to do
its job.

The best I can do is answer your question and tell you _how_
to write it.

				--Blair
				  "It's sorting those damnable
				   '...' types that'll get
				   you every time..."