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?
-
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.templatetypedef– templatetypedef2021年05月25日 16:05:09 +00:00Commented 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=2180073song– song2021年05月26日 02:11:53 +00:00Commented May 26, 2021 at 2:11