Newsgroups: comp.lang.c
Path: utzoo!utgpu!news-server.csri.toronto.edu!helios.physics.utoronto.ca!aurora.physics.utoronto.ca!neufeld
From: neufeld@aurora.physics.utoronto.ca (Christopher Neufeld)
Subject: Re: How to write a sorting program that will sort everything?
Message-ID: <1991Mar23.164807.7318@helios.physics.utoronto.ca>
Sender: news@helios.physics.utoronto.ca (News Administrator)
Nntp-Posting-Host: aurora.physics.utoronto.ca
Organization: University of Toronto Physics/Astronomy/CITA
References: <1991Mar22.005700.17663@minyos.xx.rmit.oz.au> <3403@inews.intel.com>
Date: Sat, 23 Mar 1991 16:48:07 GMT

In article <3403@inews.intel.com> bhoughto@pima.intel.com (Blair P. Houghton) writes:
>In article <1991Mar22.005700.17663@minyos.xx.rmit.oz.au> rcoahk@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.
>
   Huh? I may be relatively new to C but isn't the stdlib function
qsort() an example of a program which does just that? You pass it the
start of the array of elements to be sorted, the number of elements, and
the length of each elements, and a pointer to a user-defined comparator
function which is passed pointers to two elements, and returns an
integer value. This user-written function defines what the caller means
by "greater than/equal/less than", so any time you can conceive of a
reasonable "sort" order, you can write a function which returns '1' if
the contents of the first pointer are greater than those of the second,
'0' if they're equal, and '-1' if the first points to an elements less
than that to which the second points.
   Even if 'qsort()' is not right for your application, you can
implement any other sort program you like, with a function call to
establish the relative order of two elements.
   If there is a type of input for which "sorting" isn't defined, then
by definition you don't want to sort it. If you have your own definition
of a sort on the elements, you can sort it with that definition, even if
nobody else agrees with you on your rule. You needn't even require that
all the elements have the same type, you could sort a mixture of float
array elements, structures of addresses and phone numbers, and pointers
to functions, if you have some way to decide when one of those is
greater than another of them. For this, qsort() wouldn't work because it
accepts elements only of uniform size in contiguous memory. Your own
sort routine could do it, though.

   To answer the original question, I'd pull out any reference book on
sorting, for example a heap sort, and when you get to the line(s)
reading something along the lines of:
    if (*(a+i) < *(a+j)) {   SWAP(i,j)   }
replace that/those line(s) with:
    if (compar(a+i,a+j)) {   SWAP(i,j)   }
where compar() is a function you write to return non-zero if
*(a+i) < *(a+j)

You can modify this as necessary to check for equality and greater-than
conditions.


-- 
 Christopher Neufeld....Just a graduate student  | Too much self-love just
 neufeld@aurora.physics.utoronto.ca    Ad astra! | makes you jealous of
 cneufeld@{pnet91,pro-cco}.cts.com               | the people who envy you.
 "Don't edit reality for the sake of simplicity" |