0

I am studying radix sort and I can't understand why array accesses in radix sort is 11N+4R+1. The following is radix sort code written in Java.

int n = a.length;
String[] aux = new String[n]; //N
int[] count = new int[R + 1]; //R+1
for (int i = 0; i < n; i++) { 
 count[a[i]+1]++; } //why 3N?
for (int r = 0; r < R; r++) {
 count[r + 1] += count[r]; } //3R
for (int i = 0; i < n; i++) {
 aux[count[a[i]]++] = a[i]; } //3N(?)+N+N = 5N
for (int i = 0; i < n; i++) {
 a[i] = aux[i]; } //2N

count[a[i]+1]++; is equal to count[a[i]+1]=count[a[i]+1]+1;. I think each count[a[i]+1] has 2N array accesses so the total is 4N. If you look at the third for loop, a[i] is also duplicated at both sides in aux[count[a[i]]++] = a[i] but the right one is just counted one array access. Why does count[a[i]+1]++ count to 3N?

asked May 25, 2021 at 13:25
2
  • Which source are you using that's giving a value of 11N + 4R + 1? That would have to be specific to a particular implementation of radix sort, rather than to the more abstract "radix sort" algorithm. Commented May 25, 2021 at 16:05
  • This is from my school class material. I searched more specific code and explanation about this, but I still don't understand. informit.com/articles/article.aspx?p=2180073 Commented May 26, 2021 at 2:11

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.