• Register
Welcome to Kodlogs, programming questions and answer website.
0 votes
11 views

What is radix sort with example?

What is radix sort good for?

Why radix sort is not used?

How do I create a radix sort?

by (1.5k points)  
reshown by

3 Answers

0 votes

Radix Sort - Intro to Parallel Programming

So we've seen some really interesting algorithms so far,

but the GPU performance leader is none of the ones that we've discussed to date.

Instead, typically on the GPU for the highest performing sorts

we use a different sorting algorithm called radix sort.

Now, all of the previous sorting algorithms were comparison sorts,

meaning the only operation we did on an item was compare it to another one.

Radix sort relies on a number representation that uses positional notation.

In this case, bits are more significant as we move further left in the word,

and it's most easily explained using integers.

So the algorithm for radix sort is as follows.

Start with the least significant bit of the integer, split the input into 2 sets,

those that have a 0 with this particular bit location and those that have a 1.

Otherwise, maintain the order.

Then proceed to the next least significant bit and repeat until we run out of bits.

So as usual, we're going to do an example that will make more sense,

and we're going to use unsigned integers.

So what we're going to sort is this column of numbers to the left,

and here is the binary representation of those numbers.

And so we're going to start here with the least significant bit.

So the way that we're going to do this is take all the elements that have a 0 as the least significant bit,

and we're going to otherwise maintain their order, but we're going to put them up top.

Then we're going to take all the rest of the elements,

those that have a 1 as the least significant bit,

and we're going to again keep them in order and append them to the list that we've just created.

So what this creates is a list where all the least significant bits are 0

and then a list where all the least significant bits is 1.

Now we move to the next least significant bit,

so the bit in the middle, and we're going to do the same thing.

We're going to take all the 0s and put them up top,

and then we're going to take all the 1s and put them below.

And here the dotted lines are just showing the data movement that we're looking at.

The green lines are the ones where the middle bits are 0,

and the blue line is the one where the middle bits are 1.

Now we move on to the next most significant bit--

in this case, the very most significant bit--and we do the same operation again.

Zeroes in the most significant bit move up top, 1s move to the bottom,

otherwise, we maintain the order.

And now we have a sorted sequence. Pretty cool, huh?

Now, there's 2 big reasons this code runs great on GPUs.

The first is its work complexity. The best comparison base sorts are O(n log n).

This algorithm, on the other hand, is O(kn),

meaning the runtime is linear in 2 different things.

First, it's linear in the number of bits in the representation.

So this particular integer has 3 bits in its representation,

and it took 3 stages for us to be able to sort the input.

Second, it's linear in the number of items to sort.

So we have 8 items in the representation here,

and so the amount of work is proportional to 8.

Generally k is constant, say a 32-bit word or a 64-bit word for any reasonable applications.

And so in general, the work complexity of this

is mostly proportional to the number of items that we need to sort.

And so that's a superior work complexity to any of the sorts that we've talked about to date,

and so that's 1 reason why this looks so good.

The second is that the underlying operations that we need to do this split of the input at each step

are ones that are actually very efficient.

And in fact, they're efficient operations that you already know.

Let's take a closer look at what we're doing.

We're only going to look at the first stage of the radix sort algorithm,

where we're only considering the value of the least significant bit,

and we're only going to look at the output for which the least significant bit is 0.

Now what are we actually doing here?

We've already learned an algorithm that does this operation today.

So what is the name of the algorithm that takes this input and creates that as the output?

by (8.9k points)  
0 votes
So the answer here is that what we're going to want to do
is look at the least significant bit.
That means we'll take the bit representation of i and end it with the value 1,
which is only going to leave us with the value of the least significant bit.
And then we're going to test whether that bit is 0 or 1.
And we only want to keep the ones that are 0.
We only want this to return true if that least significant bit is 0.
by (8.9k points)  
0 votes

Radix Sort  - Intro to Parallel Programming

here is an introduction to radix sort as
an example let's say we want to sort
this array of six integers each integer
value ranging from 0 through 999 and we
want to sort this array in an ascending
order so that the smallest number comes
first the first step that we need to
take in radix sort is sorting the given
array using counting sort and the keys
that we're going to use for that will be
the last digit in each number so it's as
if using counting sort to store an array
with the values 3 9 0 6 3 & 3 in this
particular case and with that the value
that we have with the smallest key which
is there in this particular case will be
the first element in this sorted array
and after that there will be values with
the second smallest key which is 3 so 50
3 will be the second element and after
that 633 and 233 now we're going to keep
going like that until the very end and
the key thing to remember here is that
counting sort is a stable sorting
algorithm and so the values with the
same keys in this example 53 633 and 233
they appear in exactly the same order in
the storage array as they do in the
original array and it's really important
to use a stable sorting algorithm as a
subroutine for radix sort because if we
use an algorithm that's not stable it
just wouldn't work now the second step
in radix sort is sorting this new array
using counting sort again with the
second last digit in each number as the
key this time once we do that the new
sorted array will look like this and
we're going to repeat the same procedure
with this new array and this time we're
going to use the first digit as the key
and you'll notice that there are some
numbers without any number in that place
so we'll just use 0 as the key for those
numbers once that's done the whole array
is going to be sorted let's now think
about the time complexity of radix sort
first we're going to define some
variable
let's call the number of elements in the
array or the length of the array and and
it's equal to six in this particular
case because we have six elements and
that's called the number of digits that
we need to represent each number D and
we need three digits here and to
represent each number we're using the
base 10 system here and let's call that
B so B is equal to 10 in this particular
case now remember that in each step of
radix sort we sort the array using
counting sort using one of the digits as
the key and the time complexity for
counting sort is Big O of n plus K where
K is the range of keys that we have for
each number and the range of keys in
this particular case is 10 or B because
the key ranges from 0 through 9 and it's
always an integer and so each of these
steps takes Big O and plus B in time and
we need to repeat this procedure three
times in this particular case or D times
in general so the time complexity for
the whole algorithm of radix sort will
be big-oh D times n plus B and this is
quite fast when the range of input is
fairly limited compared to the number of
elements that we have in the array and
in that situation depending on the size
and the nature of the input it can
perform better than an optimal
comparison based sorting algorithm such
as quicksort or merge sort which would
take Big O of n log n in time and one
last thing to note here is that there's
a range of values that we can choose
from for the value of B we chose base 10
just for simplicity and just to show an
example but we could chosen for example
base 100 base 2 for a or any other
positive integer for that matter and
this choice will essentially come down
to making a trade-off between time and
space because the larger value that we
choose for B the more space is required
for the account resource step but at the
same time a larger B or larger base will
imply a smaller D or
less number of digits for each number so
it'll take less time to sort the array
using radix sort as long as B is less
than n
by (8.9k points)  
...