Quicksort vs Radix-Sort

Asked

Viewed 183 times

2

I’d like to know why Quicksort is more diffuse than Radix-Sort. Since the quicksort uses the comparison and Radix-Sort not the second can be faster than the(nlog(n)), and actually it’s O(Mn) where m is the number of bits used to represent the element.

Why isn’t it more fuzzy, especially for number ordering? It has something to do with caching?

1 answer

2


The Quicksort is more pliable and works well with all kinds of data, all you need to sort is the possibility to compare items. It is trivial with numbers, but can be used with other data types as well.

Radix-Sort, however, sorts things by their binary representation, it never compares items against each other.

Another factor of this diffusion is that, as you yourself gave the idea, the Radix-Sort normally needs more memory. Because it usually uses a secondary buffer to store partial results of the sort algorithm. In large amounts of data, this can generate a great loss of performance. Remembering that the use of memory will depend on the amount of bits used at each "sort", where it can overcome other algorithms.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.