Re: qsort and arbitrary types

From: glen herrmannsfeldt (gah_at_ugcs.caltech.edu)
Date: 06/10/04 

Date: Thu, 10 Jun 2004 21:10:33 GMT

James Giles wrote:
(snip)

> Well first, in many versions of QSORT (and other sorting
> routines), the actual data is not swapped around at all. Instead,
> an array of integers is produces which contains the indices into
> the data array which express the proper ordering. That is, the
> result array used as a vector subscript produces an ordered
> array: ARRAY(RESULT(:)) is ordered. Hence, you really
> only need the reference to a comparison function if your
> sort does this.

The C qsort() function will sort whatever array is passed
to it, as long as the comparison function returns the right
value. You can sort an array of pointers to structures
or array elements, of pointers to pointers, or the structures
themselves. It is up to the user to decide.

There is a section in Knuth's volume 3, Sorting and Searching,
where he considers external sort (data on tape or disk).
One could read in only the keys and sort them, along with
an indicator of the position of the record in the file,
and later reorder the records in the indicated order.
It turns out to be about as much work to reorder the data
as it would have been to sort it in the first place!

> Second, if your sort actually moves the data and doesn't produce
> a permutation of the indices, you only need a conditional SWAP
> routine. That is, the comparison and the swap can be combined in
> the same referenced procedure. That'why my comparison was
> called SWAP in the sample code I posted.

There are some sort algorithms that work that way, but
many do not. Quicksort, for each pass, involves arranging data
based on comparison with one element, so the swap and compare
can't be combined.

-- glen

Relevant Pages

  • Re: "Sorting" assignment
    ... And many others prefer to call partition exchange because "quicksort" ... bin B depending on whether it is greater than, ... If the array is already sorted, this means that you end up ... attempt to sort them. ...
    (comp.programming)
  • Re: A Fast sorting algorithm for almost sorted data
    ... far my compressor has potential but is nowhere near ready. ... It does however make heavy use of sorting. ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ...
    (comp.compression)
  • Re: problem in solving this.
    ... element is selected and placed at the end of the array. ... It looks like bubble sort to me. ... One swap per pass. ...
    (comp.lang.fortran)
  • Re: Save & Sort
    ... You can copy your array to a scratch ... "Heap" sort. ... Dim lst As Long ... Dim tmp As String ...
    (microsoft.public.excel.programming)
  • Re: fast stable sort
    ... if you have an existing array, you can simply arrange an array of ... pointers to the items, and sort that. ... hence require swapping pages of virtual memory, ... each merge run instead of accessing them in sequential RAM ...
    (comp.programming)