Re: Sorting routine

"dkelvey@xxxxxxxxxxx" <dkelvey@xxxxxxxxxxx> writes Re: Sorting routine
On Sep 5, 3:19 pm, m...@xxxxxx (Marcel Hendrix) wrote:
"dkel...@xxxxxxxxxxx" <dkel...@xxxxxxxxxxx> wrote Re: Sorting routine

On Sep 4, 12:36 pm, m...@xxxxxx (Marcel Hendrix) wrote:
"dkel...@xxxxxxxxxxx" <dkel...@xxxxxxxxxxx> writes Re: Sorting routine

[..]
\ FORTH> test ( 3 GHz PIV )
\ Creating 1,000,000 input values.
\ Sorting .. 0.126 seconds elapsed. ok


Hi Marcel
This looks right. There is room for improvements. Using RSHIFT may or
may not be the best way to parse out bytes but other methods would
be machine dependent. On a byte addressing machine it might be
more efficient to just fetch the byte at a time, rather than fetching
the entire value and then extracting the byte. On my NC4000 that
had no byte addressing, I made a hardware register at -1 that would
do a byte swap. The endian problem makes it less portable as well.

On a PC, the hardware fetches many 32-bit words at once.

As I mentioned, the two arrays, index and counts could be combined.
If kept separate, for the last pass to sort the signed values, one can
create the index array starting from the 128th entry and then
wrap back to 0 after 255, instead of starting from zero. One would
need to keep the two arrays in this method. This would only be done
as the last step when doing the byte with the sign for 2's complement.

I'll leave the complications for somebody else :-) I like the simplicity
of the current code.

I'm assuming that RSHIFT does a byte sized shift?

n RSHIFT shifts n bits.

One can do a small optimization bye building the counts and index
tables for each byte at once. This save needing to refetch the entries
for each pass to do this calculations. One still needs to run the
last step for each byte separately in order.

I am not so sure this will do much (besides decreasing size).

If there are a lot of bytes in the values, one can setup such a loop
that one does the counting at the same time as one does the placing
in the output array. This would make the first pass and last pass
unique. This would be handy for sign sorting of 2's complement.

Again, I'll gladly leave the complications to other enthusiasts.

Have you rerun any of the other benches with the faster processor
and using a 1M entries?

In all cases random numbers were used to initialize the arrays.

FORTH> simple-bench1M ( 3 GHz PIV )
Sedge sort - 1000000 elements, 174 ms (needs 128889 passes)
Quicker sort - 1000000 elements, 191 ms (needs 518998 passes)
Quick sort - 1000000 elements, 195 ms (needs 771816 passes)
Comb sort - 1000000 elements, 317 ms (needs 54 passes)
Heap sort - 1000000 elements, 913 ms (needs 19549621 passes)

So Radix/Distribution sort is about 1.4 times faster than Sedge's Sort.
However, no serious optimization effort has been done yet for either sort.

-marcel

.

Relevant Pages

  • 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: Efficiently Extracting Identical Values From A List/Array
    ... struct SortHelper ... Now sort that array according to NodeIndex: ... running through the data structure and sorting things out. ...
    (comp.lang.cpp)
  • Re: indirect sort
    ... I wrote a Comparator (I don't want to use ... Comparable in order to be able to choose the field I am sorting by) ... a way to create a doublearray of my fields I want to sort by, ...
    (comp.lang.java.programmer)
  • Re: sorting by multiple criterias (sub-sorting)
    ... and I want to sort these ... > are multiple records with the same name, sorting this group ... > name and same age, ... Quoting from "How do I sort an array by?" ...
    (comp.lang.perl.misc)
  • 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)
Loading