Questions tagged [radix-sort]
Radix sort is a sorting algorithm which sorts key/value pairs with integer keys by ordering digits.
38 questions
1
vote
0
answers
84
views
A parallel MSD radix sort in Java for long keys with near linear speedup
Intro
I have this implementation of a parallel MSD (most significant digit) radix sort. It runs in
$$\mathcal{O}\Bigg( \bigg(\frac{N}{P} + PB \bigg) \log_B \sigma\Bigg),$$ where \$N\$ is the length of ...
- 32.3k
4
votes
1
answer
158
views
Efficient least-significant digit (LSD) radix sort for int keys in Java
(This post has a continuation post.)
This one is my attempt at LSD radix sort:
Code
com.github.coderodde.util.LSDRadixsort.java:
...
- 32.3k
1
vote
0
answers
105
views
A parallel MSD radix sort in Java for integer keys
I have this repository: https://github.com/coderodde/ParallelRadixSort.java/tree/main
It contains a parallel MSD radix sort presented below:
...
- 32.3k
3
votes
2
answers
151
views
Fast portable, parallel MSD radix sort for unsigned keys in C89
Now I have this portable, parallel MSD radix sort for unsigned keys. It exhibits linear speedup on small values of \$P\$ and has a running time of
$$
\Theta(N/P + P)...
- 32.3k
2
votes
1
answer
74
views
Asking for C++ advice based on a radix sort function
Can someone point out what possible edge cases/leaks/inefficiencies my code has and how they could be avoided/fixed. Basically, I want to know what mistakes I make so I can avoid making them in the ...
- 23
6
votes
1
answer
225
views
Improving performance of radix sort
I am trying to optimize the following (now C) radix sort code for use in my game engine library. The basis for this code was inspired by this youtube video on a C++ implementation called ...
- 302
1
vote
2
answers
164
views
Radix Sort function
I am working with this assignment of optimizing a radix sort code in C++ and I need to reduce the execution time. My code is working and it looks like this:
...
2
votes
1
answer
298
views
Counting Radix Sort: A C++ version
Follow up to original question:
This is Radix Sort, using a counting implementation. For numbers that are N bytes in length, we use an N pass counting approach. Starting with the least significant ...
- 97.7k
2
votes
2
answers
226
views
Radix Sort: A C++ version
Just realized I have never implemented Radix Sort (spurred about watching a YouTube video about it). So I thought I would give it a go.
This is Radix Sort, using a counting implementation. For numbers ...
- 97.7k
4
votes
2
answers
355
views
Radix sort with benchmarks
I am trying to time radix sort on 128 bit unsigned integers for different base sizes (that I call bitwidth). My code has at least the following problems:
The radix sort itself may run slower than it ...
- 231
3
votes
2
answers
264
views
Sorting an array of positive integers including 0 much faster than Radix Sort
I was working on an Limit Order Book structure in JS and came up with this algorithm. I am pretty sure this must have already been implemented but couldn't even find a clue over the web.
The thing is, ...
- 946
4
votes
2
answers
168
views
Radix Sort Speed
I have implemented a radix sort algorithm in Python 3. It first finds the maximum number of digits in the list, then changes them to strings and adds 0's. For example, [7, 23, 107, 1, 53] to ['007', '...
- 113
1
vote
1
answer
244
views
MSD Quick Radix Sort in Place in C++, Object/Pointer Oriented
Memory: O(log2(max)*2)~O(1)
Speed: O(log2(max)*n)~O(n)
so i did before a MSD Radix Sort in place but i wanted to do one, with out the count, So i join together the quick sort and radix sort. Think as ...
1
vote
1
answer
306
views
MSD Radix sort in Place in c++, Object/Pointer Oriented
Memory:O(log(max)base(mod)*mod)Speed:O(log(max)base(mod)*n)
I did a radix sort in place to not get a auxliar array. In the process i discorver a few things.
Is imposible to do LSD radix sort in place ...
1
vote
1
answer
123
views
LSD radix sort (force avoid div or idiv compiler instruction) in C++
I was trying to optimize the Radix Sort code, just because. Nothing more, nothing less. Here it is!!! So tell me, how does it look?
Summary:
instead of a div or mod ,i use left shift and right shift ...