When you have an an unsorted array and want k-th largest value, Selection algorithm comes to the rescue. No need to sort the array, as that’s too much work and is much slower, but instead Selection can be used. Selection algorithms are in-place, with most at least expected linear-time, and some worst-case linear. In this […]
Read more "Partition is Not Required For Selection"Most algorithms books describe LSD and MSD Radix Sort variations. However, they do not cover in-place variations. Wikipedia does not describe it either. In this blog I describe an in-place MSD Radix Sort. This is a simpler variant to describe than the type I’ve developed and discussed in previous blogs and in my “Practical Parallel […]
Read more "In-Place MSD Radix Sort Explained"Like the Selection algorithm, described in several previous blogs, Partition is another algorithm closely related to sorting. Given a single value or an array of values, the Partition algorithm splits the array into sections with useful statistical properties, without sorting it, in linear time – i.e. O(n). For example, Partition can split an array into […]
Read more "Radix Partition"Selection is an interesting algorithm related to sorting. k-th value Selection, provides the k-th largest value within an unsorted array of values without sorting the array. It does this in linear time, while using comparisons, which is faster than comparison sorting algorithms are capable of. Comparison-based Selection algorithm was developed over 50 years ago. Non-comparison […]
Read more "k[]-th Radix Selection"Problem: You have an array of a billion numeric keys (e.g. 32-bit unsigned integers) and need the largest 11 of them. Solutions: The first two solutions do more work than is necessary, as they sort all of the array elements, including the top 11 elements. This was not required by the problem statement. The whole […]
Read more "Top-K Radix Selection Algorithm"I’ve been optimizing variety of Radix algorithms for over a decade: LSD and MSD Radix Sort, Single Core and Multi-Core, and Radix Selection. Several of these optimization techniques can be applied to all of these algorithms. In this blog, I’ll discuss each of these optimizations and show how much performance is gained, for sequential single […]
Read more "Fastest LSD Radix Sort in C++ on a Single CPU Core"I ran across a research paper recently on Radix Selection where the authors mentioned that LSD Radix Sort is known to have performance issues when sorting arrays of data with certain distributions. They did not elaborate what those distributions were. Also, Professor Sedgewick has mentioned that the worst case for Radix Sort is when the […]
Read more "Optimizations of LSD Radix Sort for Different Input Data Distributions"One performance optimization that was introduced in the Radix Selection algorithm can also be applied to the MSD Radix Sort – combining counting with the permutation phase. This optimization cannot be done during the first digit pass, since counting must be performed first to figure out the bins to permute the data into. However, during […]
Read more "MSD Radix Sort Optimization"In my previous blog post on Radix Selection, the algorithm which returns the k-th largest value from an unsorted array was shown to be significantly faster than sorting, because it performs less work. In this blog, I’ll explore further optimizations to make Radix Sort even faster. More Bits Per Digit Radix Sort (LSD and MSD […]
Read more "Radix Selection Optimizations"There is a closely related algorithm to sorting called Selection, which provides the k-th element from an unsorted array. For example, a 17-th highest test score from a college Physics class, or a 91-st most popular book at the library. One way to accomplish Selection is to sort the array and then access the k-th […]
Read more "Radix Selection Algorithm"
Algorithm Performance 