Radix sort
Posted: Tue Mar 09, 2010 5:35 pm
This is a very cool sorting algorithm. It's not as fast as PB's sort, but not exactly slow either. Unfortunately it sorts negative numbers in reverse (or actually, the positive numbers are sorted in reverse, but if you reverse this, then the negative numbers come out in reverse). But I bet this can be fixed.
Algorithm
1. Sort the list in place based on the most significant ("leftmost") bit. This splits the list in two (the entries with this bit=1 is list 1, the entries with this bit=0 is list 2).
2. Use the first step of this algorithm on both list 1 and 2, except use the next most significant bit (one bit "to the right" of the one we used in the previous step).
So how do we sort the list based on a particular bit? We use another sort, I called it "bit selection sort", it's selection sort, but because the keys are only one bit long, we can do some special optimizations.
Selection sort works like this:
0. Set I = 0
1. Find the maximum item in the unsorted part of the list, and swap this with the item at position I
2. Increase I by 1
3. If we are not at the end of the list yet, go to step 1.
But since we sorting on bits, we have an advantage: since the maximum value of a bit is 1, we know immediately if find a bit that's 1, that no other item has a higher bit value. So we don't have to traverse the entire unsorted part of the list to find each maximum value. We just have to find ANY entry with bit value 1. So it's faster.
To avoid unnecessary swapping, we start looking for the "maximum" (bit = 1) bit from the END of the list. This optimization will cause the sort to unstable, so if you need a fast stable sort you could probably get that by looking from the current position (I) instead of from the end of the list (I didn't test it, though).
Note that by searching the internet, you may come across descriptions of "radix sort" which uses pigeonhole sort instead of bit selection sort. This would be completely ok except that they don't explain which part of the code is pigeonhole sort and which part is the actual radix sort, and just call everything "radix sort". So don't let this confuse you.
Algorithm
1. Sort the list in place based on the most significant ("leftmost") bit. This splits the list in two (the entries with this bit=1 is list 1, the entries with this bit=0 is list 2).
2. Use the first step of this algorithm on both list 1 and 2, except use the next most significant bit (one bit "to the right" of the one we used in the previous step).
So how do we sort the list based on a particular bit? We use another sort, I called it "bit selection sort", it's selection sort, but because the keys are only one bit long, we can do some special optimizations.
Selection sort works like this:
0. Set I = 0
1. Find the maximum item in the unsorted part of the list, and swap this with the item at position I
2. Increase I by 1
3. If we are not at the end of the list yet, go to step 1.
But since we sorting on bits, we have an advantage: since the maximum value of a bit is 1, we know immediately if find a bit that's 1, that no other item has a higher bit value. So we don't have to traverse the entire unsorted part of the list to find each maximum value. We just have to find ANY entry with bit value 1. So it's faster.
To avoid unnecessary swapping, we start looking for the "maximum" (bit = 1) bit from the END of the list. This optimization will cause the sort to unstable, so if you need a fast stable sort you could probably get that by looking from the current position (I) instead of from the end of the list (I didn't test it, though).
Note that by searching the internet, you may come across descriptions of "radix sort" which uses pigeonhole sort instead of bit selection sort. This would be completely ok except that they don't explain which part of the code is pigeonhole sort and which part is the actual radix sort, and just call everything "radix sort". So don't let this confuse you.
Code: Select all
Procedure BitSelectionSort(Array Arr.l(1), Start, Stop, Bitmask)
Fill = Start
Look = Stop
While Arr(Fill) & Bitmask
Fill + 1
If Fill > Stop
ProcedureReturn Fill
EndIf
Wend
While Look > Fill And Fill <= Stop
If Arr(Look) & Bitmask
Swap Arr(Fill), Arr(Look)
Fill + 1
While Arr(Fill) & Bitmask And Fill <= Stop
Fill + 1
Wend
EndIf
Look - 1
Wend
ProcedureReturn Fill
EndProcedure
Procedure RadixSortIn(Array Arr.l(1), Start, Stop, Bitmask.l)
If Bitmask
Pivot = BitSelectionSort(Arr(), Start, Stop, Bitmask)
Bitmask = (Bitmask >> 1) & $7FFFFFFF ; & 7f to compensate for the use of arithmetic shift
If Pivot - Start > 1
RadixSortIn(Arr(), Start, Pivot-1, Bitmask)
EndIf
If Stop - Pivot > 0
RadixSortIn(Arr(), Pivot, Stop, Bitmask)
EndIf
EndIf
EndProcedure
Procedure RadixSort(Array Arr.l(1))
RadixSortIn(Arr(), 0, ArraySize(Arr()), 1 << 31)
EndProcedure
L = 6000000
Dim Bubble.l(L)
Dim PB.l(L)
Dim Radix.l(L)
For I = 0 To L
Bubble(I) = Random(2147483647)
Next
For I = 0 To L
Radix(I) = Bubble(I)
PB(I) = Bubble(I)
Next
time = ElapsedMilliseconds()
RadixSort(Radix())
MessageRequester("", Str(ElapsedMilliseconds()-time))
time = ElapsedMilliseconds()
SortArray(PB(), #PB_Sort_Descending)
MessageRequester("", Str(ElapsedMilliseconds()-time))
For i = 0 To L
If Radix(I) <> PB(I)
MessageRequester("", "Error in sort at " + Str(I))
End
EndIf
Next