Re: Sort using Integrated Histograms
 From: dcorbit@xxxxxxxxx
 Date: 16 Oct 2006 17:24:45 0700
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 lowmid 8 bits, the highmid 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 lowmid
8 bits and the corresponding (altered) histogram. And so on with the
highmid 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
.
 FollowUps:
 Re: Sort using Integrated Histograms
 From: persimmonseven
 Re: Sort using Integrated Histograms
 References:
 Sort using Integrated Histograms
 From: persimmonseven
 Sort using Integrated Histograms
 Prev by Date: Re: int or long int?
 Next by Date: Re: C Source code for Integration & differentiation
 Previous by thread: Sort using Integrated Histograms
 Next by thread: Re: Sort using Integrated Histograms
 Index(es):
Relevant Pages
