Questions tagged [radix-sort]
Radix sort is a sorting algorithm which sorts key/value pairs with integer keys by ordering digits.
37
questions
1
vote
0
answers
51
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:
...
- 27k
3
votes
2
answers
101
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)...
- 27k
1
vote
1
answer
52
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 ...
- 13
6
votes
1
answer
176
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
114
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
214
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 ...
- 93.9k
2
votes
2
answers
144
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 ...
- 93.9k
4
votes
2
answers
290
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 ...
- 191
3
votes
2
answers
197
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, ...
- 856
4
votes
2
answers
140
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
212
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
253
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
93
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 ...
3
votes
2
answers
56
views
Radix sort is deceiving
I wanted to compare radix_sort to quick_sort for values limited to 0..127 so I implemented this :
...
- 975
0
votes
1
answer
87
views
Time complexity of radix sort
I read time complexity of radix sort is O(wn) or O(n log n), if all n numbers are distinct. After implementation it look to me as if I have implemented radix sort which has time complexity of O(n ^2). ...
- 171
1
vote
1
answer
180
views
Radix sort function in R
I know that sort in R uses radix sort, and I played around in implementing it (mainly to be sure I understood the algorithm properly). However, my implementation is ...
- 121
1
vote
1
answer
2k
views
3
votes
1
answer
722
views
Radix sort implementation in JS (LSD)
I have written LSD radix sort implementation in JavaScript (6 functions in total).
It sorts positive and negative integers:
...
- 133
1
vote
0
answers
200
views
Radix trie optimization
I have got a list of Users that I want to filter using text typed in TextView. I want it to be a smart filter, something like searching contacts in contact book on ...
- 133
6
votes
2
answers
207
views
Radix Sort Efficiency
I'm implementing a (hopefully) efficient MSB Radix Sort in Java. My current implementation isn't efficient enough for my use-case (see bottom for a brief performance comparison against ...
- 249
5
votes
1
answer
344
views
Radix Sort speed improvement
I was trying to optimize the Radix Sort code, because I never found a code that was simple and easy to understand yet wasn't any slower. I have seen codes on web and in some books that implement ...
- 151
2
votes
2
answers
362
views
Radix sort implementation
I have a problem where I need to sort an extremely large number of numbers but the numbers are in a narrow range (0..r-1) where r is typically around 10, and after googling around a bit it seemed like ...
- 277
3
votes
2
answers
1k
views
Implementing RadixSort using JavaScript
Can someone review my code? I am trying to implement radix sort in JavaScript.
...
- 145
4
votes
2
answers
2k
views
Implement LSD radix sort in python
I'm trying to implement LSD radix sort in python, but my code used 4 loop, is there any way I can do it in three or less?
Here is the 4 loops:
First loop iterate through the input list, convert it ...
- 43
0
votes
1
answer
2k
views
MSD radix sort in C
This time, I have rewritten my radix sort implementation from C++ to C:
integer_sort.h:
...
- 27k
0
votes
1
answer
2k
views
Radix sort in Java
As homework I had to implement many sorting algorithms including radix sort in Java. The task is to sort doubles in the range [0-1) that are rounded to the 10th ...
1
vote
1
answer
3k
views
8
votes
1
answer
2k
views
Implementing LSD radix sort
I would love a code review of this LSD radix sort implementation. I've rolled my own, and have implemented counting sort as well. I feel like some of the data structures I've chosen could be improved. ...
- 1,331
7
votes
1
answer
678
views
Radix sorts in Java
I was curious, how in-place radix sort compares to the variant which uses an auxiliary array in order to speed up the sorting. I implemented both and tested it against ...
- 27k
3
votes
2
answers
2k
views
Radix sort with integer divisions
Here's a perhaps naive but simple implementation of Radix sort in Java.
It works with any radix, and both positive and negative numbers.
...
- 111k
3
votes
3
answers
6k
views
Radix sort with C++
At first the input array is traversed and for each number the lsb is found. Then the number is put into appropriate bucket according to it. For example for an input array { 123, 45}, at first 123 will ...
- 239
3
votes
1
answer
1k
views
Parallel MSD radix sort in Java
I have this parallel implementation of MSD radix sort, which processes the entries by one particular byte. At each byte index, it has three phases:
Count the bucket sizes.
Insert each entry to its ...
- 27k
4
votes
1
answer
815
views
MSD radix sort in Java for parallel arrays - follow-up
The previous and initial iteration at MSD radix sort in Java for parallel arrays.
Changes:
Entry hides both the sort key and satellite datum in private final ...
- 27k
3
votes
1
answer
736
views
MSD radix sort in Java for parallel arrays
I have this MSD (most-significant digit) radix sort sorting Entry objects holding a sorting key of type long and a satellite ...
- 27k
4
votes
1
answer
1k
views
Radix sort (LSD) and counting sort
I'm reading CLRS, and to practice, I rolled my version of radix sort and counting sort. I was looking at some reference implementations, particularly the LSD one from Rosetta Code, and mine performs ...
- 393
16
votes
4
answers
5k
views
Least significant digit (LSD) radix sort of strings
I am learning string algorithms and wrote this C example based on a Java example I found online. Any feedback relating to style, code clarity, whether it is generic enough to be re-used, interface, ...
- 2,449
6
votes
1
answer
5k
views
Stable radix sort in-place using O(1) space
I am trying to implement a stable radix sort in place with O(1) space. I've seen Wikipedia, and I notice the C implementation is using a temporary variable to hold the sorted value for each pass, and ...
- 163