Questions tagged [radix-sort]
The radix-sort tag has no usage guidance.
43 questions
1
vote
1
answer
96
views
The value of $r$, with $r≤ b$, that minimizes the expression $(b/r)(n+2^r)$ in the analysis of the radix-sort algorithm
In chapter 8 of the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein, lemma 8.4 is proved. (my question is after the proof of the lemma)
Given $n$ $b$-bit numbers ...
- 121
0
votes
0
answers
42
views
Could Radix Sort be used to tackle LCS algorithm?
Could one use the Radix Sort to find the Longest Common Subsequence problem? I am new to algorithms and was wondering if the string was converted to a list and then one was able to apply Radix Sort ...
- 101
3
votes
0
answers
65
views
GPU compute parallel radix sort optimizations
I'm looking at [1] that describes a GPU parallel radix sort algorithm. They describe multiple optimizations but in section 3 where the whole algorithm is described some things elude me.
First, the ...
- 141
0
votes
0
answers
165
views
Radix sorting for pairs of numbers
I'm struggling with implementing O(n+k) radix sorting algorithm for pairs of numbers which values are constrained .
For example
below is array of {x,y} before and after using modified radix sort ...
- 1
2
votes
1
answer
450
views
Can Radix Sort be modified for signed ints and/or floats?
A few months ago I learned about the magic that allows radix sort to run in O(n) time and space. Most tutorials on radix sort say it is useful for very large ...
- 121
-1
votes
1
answer
136
views
Sorting elements into k subarrays
Given are $n$ integer numbers in the range $0$ to $5n$.
A SubSort algorithm organizes the numbers into $k=n/100$ sets,
$s_{1}$, …, $s_{k}$ , each containing $100$ numbers, such that the
following ...
- 231
3
votes
0
answers
162
views
How to detect when to use radix sort in runtime
I'm implementing a stable integer sorting algorithm, I've chosen radix sort. I've tested LSD vs MSD implementation, wrote MSD/LSD hybrid implementation to reduce bandwidth pressure. The repo is here: ...
- 131
1
vote
1
answer
206
views
Calculating the Time complexity using Radix sort
Im trying to determine what is the time complexity of sorting numbers with a specific range and base.
I have n numbers in the range of 1-n^10 and the base for the radix sort is n/log n.
I have tried ...
- 13
1
vote
1
answer
506
views
Complexity of Radix Sort
I am a little confused by the complexity proof of Radix Sort.
For counting sort, the complexity reported is $O(n+R)$, where $n$ is the number of items and $R$ is the range.
But this is not entirely ...
- 113
1
vote
1
answer
222
views
Can radix sort reach exponential time complexity?
For example, assume the input array is $$[121212,212121]$$
Say we are in base 10, so count sort will work in $O(n)$ time. We have 6 iterations which is approximately $n^2$. Is this a worst case ...
- 83
0
votes
0
answers
36
views
Analysis of Radix sort of $n$ $b$ bit numbers
I was reading radix sort in Introduction to Algorithms by CLRS . And it gave the following Lemma with its analysis
I understood the proof of the Lemma but confused on the part where they try to ...
0
votes
1
answer
202
views
Radix sort slower than Quick sort?
I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below:
...
- 295
1
vote
1
answer
1k
views
Quick Sort vs Radix Sort
In an coding exam, I was once asked this question:
Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you ...
2
votes
1
answer
2k
views
MSD vs LSD Radix sort
I read the following in CRLS:
I don't understand the text in yellow. Why would radix sort not work so well if we sort by their most significant digit? What extra "...
- 316
0
votes
0
answers
146
views
Given n strings, how to output their order after k phases of the radix sort (huge constraints)?
Disclaimer
This is not from an ongoing contest, this is from my course of ITMO on edx.org, which is a paid code so I cannot give you a direct link to the course.
Problem
You are given $\...
- 233
1
vote
1
answer
2k
views
radix-sort with different bases
So i understand how to use radix-sort in base 10 and utilize mod 10 to go through the numbers. But not sure about 2,8 or 16.
Does it follow the same idea? and i read somewhere that i need to pass ...
-2
votes
2
answers
158
views
For sorting 10^9 unique 9-digit numbers, would radix sort or counting sort be faster, and why?
For sorting $10^9$ unique 9-digit numbers, would radix sort or counting sort be faster, and why?
I know that radix sort is $O(nk)$ and counting sort is $O(n+k)$, but can’t understand how to apply ...
- 1
3
votes
2
answers
5k
views
Why does Radix sort require stable digit sorts?
I'm reading the CLRS book and have a question about the following quote from the book.
In order for radix sort to work correctly, the digit sorts must be stable.
Why is stability required? Wouldn'...
- 143
5
votes
2
answers
22k
views
Time and space complexity of Radix sort
I had previously asked a question on space complexity of radix sort here. I have also read this question. However, I still get confused about it which means that the concept is not clear. I have the ...
- 165
1
vote
2
answers
820
views
Best time complexity of sorting numbers in range [1...n log n]
given an array $A$ of $n$ numbers in range $1$ to $n\log n$, what is the time complexity of the best method to sort them?
The answer is $O(n)$ but I don't understand this. of course counting sort ...
- 307
3
votes
1
answer
2k
views
Fast, stable, almost in-place radix and merge sorts
I've developed LSD radix sort algorithm that is
stable,
about as fast as the classic LSD radix sort,
require only $O(\sqrt{RN})$ extra space when we sort into R buckets.
The same technique also ...
- 2,043
2
votes
2
answers
595
views
Time complexity of expanding decimal to new base
There is already a post on this topic on stackoverflow.
Nevertheless, I am asking the question here again, primarily because I do not understand the answer given there, and also because I have some ...
- 83
3
votes
1
answer
841
views
What is the best way to algorithmically sort physical boxes?
I work part time at UPS. Part of my job consists of taking boxes from in front of me, determining if the correct cage (1 of 6 moving cages) is behind me (true about 50% of the time), and then putting ...
- 133
1
vote
1
answer
214
views
Comparison Based Sorting Run-time with respect to Total Number of Bits of Input
Comparison-based sorting algorithms are lower bounded by $\Omega(nlogn)$, where $n$ is the number of elements in the input list.
However, when dealing with different models of computation, such as ...
- 221
1
vote
1
answer
438
views
Total Number of Bits Needed to Represent a List of N elements
This is an excerpt from the algorithms textbook How to Think About Algorithms by Jeff Edmonds (This book is a gem by the way).
I get his conclusion about Merge/Quick/Heap sorts having $O(NlogN)$ ...
- 221
3
votes
1
answer
2k
views
Radix, merge, counting sort and when to use
Okay can't figure this out. I want to make sure I understand it.
There are n random keys each being float numbers with p decimal places.
So, for example,
123.456,
343.645,
234.543,
863.238,
956....
- 51
1
vote
1
answer
746
views
Sorting an array in linear time
I need to find a method to sort an array in $O(n)$ time complexity.
I saw this link,
however I'm not sure how to apply it to the elements I need.
Input: an array $A$ of length $n$, containing values ...
- 185
0
votes
1
answer
68
views
Sorting an array of length $n$ in $O(m+n)$ time
I need to find a method to sort an array in $O(m+n)$ time complexity.
I understand it should be a variation on Radix sort, however I am not familiar with it or its implementation...
Input: an array $...
- 185
1
vote
0
answers
53
views
Find fastest sort for given range of numbers
I encountered a question from a test that I cant understand the answer
given a range of numbers $[0...(logn)^{logn}-1]$ we need to find the quickest sort available and give his running time
now ...
- 209
0
votes
1
answer
278
views
How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time?
I need to write a sorting algorithm which will sort an array $A[1..n]$, $1 \le i \le n$ such that $A[i] \in \{1,2,..,n^5 \}$, all numbers are positive integers in $\Theta (n)$ time.
The solution must ...
- 527
3
votes
1
answer
1k
views
Why does radix sort work?
I understand how radix sort works and how to implement it, but I don't understand why it works.
Are there any underlying mathematical or logical principles that it relies on?
- 141
1
vote
0
answers
99
views
Radix sort with 2 digit elements [closed]
How can we prove that radix sort correctly sorts an array of 2 elements with 2 digits each ?
- 103
3
votes
3
answers
454
views
O(n) sorting array by value - get indexes
I am in search of a linear-time sorting algorithm that is capable of returning an array B of indices A, sorted on the value of the corresponding element of A.
For example:
Input = [2, 6, 8, 9, 1, 7, ...
2
votes
0
answers
482
views
Fastest in-place sorting algorithm for Epochtime
I need to sort a lot of rows (from 1GB to 3GB) by EpochTime (a single value of every row).
What is the fastest in-place sorting algorithm for this task? Radix Sort?
I would like the fastest sorting ...
- 129
1
vote
1
answer
934
views
Which pass do you look at for Radix Sort stability?
I know this is a fairly poorly worded question, but I can't think of a better way to phrase it in the title.
So in Radix Sort, you go digit by digit from least significant to most significant, and ...
0
votes
3
answers
310
views
How do I sort these elements in O(n) time?
So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix ...
- 37
2
votes
1
answer
1k
views
Radix sort and changing bases
I have recently learned about radix sort.
I am aware that you can change the base of the numbers you need to sort but I don't really understand why this is good for the radix sort.
Radix sort runtime ...
- 123
0
votes
1
answer
236
views
Compare vs Radix
Is it better to use comparison or radix sort to sort a long sequences of java int array?
I know that I should probably use mergesort (NlogN) for comparison sort, since it is one of the fastest and ...
1
vote
1
answer
4k
views
I can not see why MSD radix sort is theoretically as efficient as LSD radix sort
Here is the pseudocode for LSD radix sort from http://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf
...
- 639
8
votes
1
answer
3k
views
Is radix sort really O(n) for sorting 32 bit integers?
I was trying to analyze radix sort in terms of time and space. Assume that we are given $n$ 32-bit integers which we would want to sort by looking at the least significant digits first.
$k$ is the ...
- 639
1
vote
2
answers
1k
views
Sorting in O(n) time in a finite domain
I've been stuck with this problem for 2 weeks. Any idea of how to aproach it?.
Let $L$ be a list of $n$ different integer numbers, assume that the elements of $L$ are in the range $[1,750]$. Design ...
23
votes
3
answers
12k
views
Practical Applications of Radix Sort
Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $[0\dots n^k -1]$ for example. If $k<\lg n$ you just convert the ...
- 2,941
8
votes
2
answers
8k
views
how does the parallel radix sort work?
I'm currently learning computer science, and there is a slide of notes brief described the parallel radix sort under data parallelism.
...
- 805