Radix Sort Using Binary

Question

I want to know if it is more efficient to use a Radix sort with Integer values or to convert the values to Binary and then sort them.

Can someone explain to me the pro's and con's of sorting values using a Radix sort with Binary numbers instead of just using Integers?

For example, I want to sort 5 values. (170, 2, 19, 40, 100)

Using a radix sort what would the Pro's and Con's be of using their binary representations? (010101010, 0010, 010011, 0101000, 01100100)

Can you explain the difference between Integers and Binary numbers? And how you convert from the former to the latter? — Scott Hunter
– Scott Hunter, Commented Dec 21, 2015 at 19:14

Danny_ds · Accepted Answer · 2015-12-27 01:41:07Z

1

Radix sort is all about sorting binary numbers. Luckily for us, integers are binary numbers too (amongst the best binary numbers actually).

Another advantage of using the binary form is that we can group on 10 bits instead of 8 bits if we want. For example, for numbers ranging from 0 - 1000000, 2 x 10 bits could be used for grouping/sorting.

Check this for an interesting read, and this for a cool animation.

answered Dec 27, 2015 at 1:41

Danny_ds

11.4k1 gold badge26 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

temp · Accepted Answer · 2015-12-21 19:21:05Z

0

With a Radix sort, when using Binary, it will require you to take more passes however you will use less queues.

When using Integers, you will use less passes, but will require more queues.

I'm not quite sure what this means in terms of Big O.

answered Dec 21, 2015 at 19:21

temp

6391 gold badge8 silver badges22 bronze badges

Collectives™ on Stack Overflow

Radix Sort Using Binary

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related