Questions tagged [radix-sort]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
24 views

Radix Sort - Base converting

I have some difficulties with calculating base for computing time complexity. Given n integers in [0...nlogn-1]. What is the time complexity in worse case scenario of the best way of sorting given ...
0
votes
0answers
61 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 $\...
0
votes
1answer
83 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
2answers
49 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
vote
1answer
492 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'...
3
votes
2answers
6k 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 ...
1
vote
2answers
201 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 ...
3
votes
1answer
587 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 ...
1
vote
2answers
67 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 ...
3
votes
1answer
101 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 ...
1
vote
1answer
76 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 ...
1
vote
1answer
110 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)$ ...
2
votes
1answer
631 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....
0
votes
1answer
166 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 ...
0
votes
1answer
44 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 ...
1
vote
0answers
44 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 ...
0
votes
1answer
187 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 ...
1
vote
1answer
567 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?
1
vote
0answers
73 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 ?
3
votes
3answers
146 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
0answers
306 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 ...
1
vote
1answer
705 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
3answers
172 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 ...
2
votes
1answer
658 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 ...
0
votes
1answer
185 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
1answer
3k 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 ...
5
votes
1answer
2k 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 ...
1
vote
2answers
887 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 ...
20
votes
3answers
8k 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 ...
5
votes
2answers
2k 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. ...