Re: Sort using Integrated Histograms


persimmonseven@xxxxxxxx wrote:
Here is an algorithm I am working on at the moment. I don't suppose it
is novel as it is very simple.
The nice thing is it sorts in linear time.

I show how to sort 32 bit unsigned integers. The algorithm is easily
adapted to signed intergers and floating point numbers.

First create 4 histogram tables with 256 entries in each.
Go through the numbers to be sorted in turn extracting the lowest 8
bits, the low-mid 8 bits, the high-mid 8 bits, and the highest 8 bits
adding 1 to the relevant entry in the corresponding histogram table.
Next you shift the entries in the histograms forward by one. Hence
the entry for 0 will have been shifted to the entry for 1. The entry
for 1 will have been shifted to the entry for 2 and so on.
Put 0 in the entry for 0.
Next you integrate the histograms: Add the entry for 1 to the entry
for 2, add the updated entry for 2 to the entry for 3 and so on.
The histogram entries have now become position pointers.
Next you partially sort the numbers by their lowest 8 bits and the
corresponding (altered) histogram: For each number in turn you look in
the entry indicated by the 8 bits and move the number to the indicated
position in a new array. You then add 1 to the position pointer in the
entry.
The result is a parially sorted list of numbers.
You next repeat the process with the parially sorted list, the low-mid
8 bits and the corresponding (altered) histogram. And so on with the
high-mid 8 bits and the highest 8 bits. Done!

You can of course use different numbers of bits and histogram tables
depending on what is best.

Sean O'Connor 15 October 2006

Your algorithm has another name:
LSD Radix sort.
http://www.google.com/search?hl=en&q=lsd+radix+sort

.

Relevant Pages

  • Sort using Integrated Histograms
    ... Here is an algorithm I am working on at the moment. ... First create 4 histogram tables with 256 entries in each. ... adding 1 to the relevant entry in the corresponding histogram table. ... The histogram entries have now become position pointers. ...
    (comp.programming)
  • Re: Histogram without deliberately putting xtics ?
    ... I would like to do a histogram (with old_val and new_val "clubbed' ... together for each entry. ... of what you want the plot to look like? ... set style histogram cluster ...
    (comp.graphics.apps.gnuplot)
  • Histogram without deliberately putting xtics ?
    ... I would like to do a histogram (with old_val and new_val "clubbed' ... together for each entry. ... in xtics? ... i really don't care if it shows just numbers ...
    (comp.graphics.apps.gnuplot)
  • Re: Help required please ( reading old writing)
    ... marriage..well sort of. ... I found an entry that said his Mum and Dad ... There was a lovely expression used for women who gave birth soon after ...
    (uk.people.silversurfers)
  • Re: Help required please ( reading old writing)
    ... marriage..well sort of. ... I found an entry that said his Mum and Dad ... the term *bidey in * ...
    (uk.people.silversurfers)