Quicksort vs Radix-sort

2

I'd like to know why Quicksort is more fuzzy than Radix-sort . Since the quicksort uses as a basis for the sort order and radix-sort the second can not be faster than O < in n ), and in fact it is mn where m is the number of bits used for represent the element.

Why is not it more diffuse, especially for sorting numbers? Does it have something to do with caching?

    
asked by anonymous 10.08.2018 / 14:37

1 answer

2

Quicksort is more flexible and works well with all data types, all you need to order is the ability to compare items. It is trivial with numbers, but can be used with other data types as well.

Since Radix-sort, it orders things by their binary representation, it never compares items against each other.

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

    
10.08.2018 / 15:21