Menu
I want to sort integers and I know radix sort is supposed to be awesome for it. Any library implementation for this sort?
527
Radix Sort is the answer. The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.
Weaknesses of Radix SortFor very large numbers or a number system with a wider base, radix sort can perform in linear time; however, the subroutine sort requires larger space for the auxiliary array it uses to sort. This increases the space requirements, making it not ideal for such cases where space is important.
Radix sort is a sorting algorithm that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order. Suppose, we have an array of 8 elements. First, we will sort elements based on the value of the unit place.
Radix Sort is a stable sort because it maintains the relative order of elements with equal values. Radix sort algorithm may be slower than other sorting algorithms such as merge sort and Quicksort if the operations are inefficient.
Depends on how strictly you define radix sort, since Boost 1.58.0 includes Spreadsort, which is a hybrid sorting algorithm that heuristically mixes bucket and comparison sorting.
For sorting integers and with no requirement for worst-case Θ(n) efficiency, Spreadsort should satisfy you.
For argument's sake, you can also take a look at my implementation of LSD radix sort, which is fairly inefficient with memory but occasionally faster than Spreadsort. You only require the radix_sort branch but I've linked to the speed_test branch because it has the readme.
68
The more actual answer is Yes since 1.58 it does:
It has something known as SpreadSort and will "magically" detect optimized paths for types like std::string, or floating point numbers that can be treated as byte arrays.
30
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
