I have attached the answer below but i don\'t understand how to get it 7) \"Coun
ID: 3848481 • Letter: I
Question
I have attached the answer below but i don't understand how to get it
7) "Counting sort" processes an array a of integers by counting how many of each number occurs in a, then assigning the elements of a to the result array b using the counts to determine their locations. It is implemented by the static method countingsort. returns a sorted copy of a, assuming that it contains only integers in the range 0 k-1 public static int counting Sort int a, int k) int counts new int [kl for (int x a) counts [x]++; int total 0; for int i 0; i ki i++) int old Count counts [i] counts [i] total total oldCount int result new int [a length] for (int x a) result counts [x] x; counts [x]++; return result; a) Show how the application countingsort (13, 7,1, 3, 8,2, 11, 10) is processed. In particular, show the state of the array counts at the end of the first loop, and at the end of the second loop, and how counts and result change during the third loop. (7 marks) b) Comment on the performance of Countingsort, as formally as you can. (3 marks) For what data will the algorithm be especially fast?Explanation / Answer
According to your question
a={ 3,7,1,3,8,2,1} to be sorted
k= 10 -> array length for count array
So we create the array of count
index
0
1
2
3
4
5
6
7
8
9
element
0
2
1
2
0
0
0
1
1
0
To put the element in count array, we follow the below procedure
since 0 is not present in a[], so count[0] = 0;
since 1 is present two times in a[], so count[1]=2
since 2 is present one time in a[] so count[2]=1
since 3 is present two times in a[] so count[3]=2
since 4,5,6 is not present in a[], so a[4]=0, a[5] =0, a[6]=0;
since 7 is present one time in a[] so a[7] =1;
since 8 is present one time in a[], so a[8]=1;
since 9 is not present in a[], so a[9]=0;
now modify the count[] array such that each element at each index stores the sum of previous counts.
Note::-> it starts the counting after second loop so we get
count[]=
index
0
1
2
3
4
5
6
7
8
9
element
0
0
2
3
5
5
5
5
6
7
count[0] =0
count[1] = 0+0=0
count[2]= 0+2 = 2
count[3]= 2+1=3
count[4]= 3+2= 5
count[5] =5+0=5
count[6]= 5+0=5
count[7]= 5+0=5
count[8] = 5+1=6
count[9] = 6+1=7
The modified count array indicates the each object in the result array
We create the result array of size n = no. of element in a =7
result =
index
0
1
2
3
4
5
6
element
0
0
0
3
0
7
0
now we see a[0] = 3
it means
count[]=
index
0
1
2
3
4
5
6
7
8
9
element
0
0
2
3
5
5
5
5
6
7
So we put result[3] = 3
And 3+1=4
Count=
index
0
1
2
3
4
5
6
7
8
9
element
0
0
2
4
5
5
5
5
6
7
Now we see a[1] =7 present at fifth position
Count=
index
0
1
2
3
4
5
6
7
8
9
element
0
0
2
4
5
5
5
5
6
7
So we put in result[5] = 7
And 5+1=6
Count=
index
0
1
2
3
4
5
6
7
8
9
element
0
0
2
4
5
5
5
6
6
7
and so on....
if you need any help regarding this question just leave comment
if you like the solution , grade it thanks
index
0
1
2
3
4
5
6
7
8
9
element
0
2
1
2
0
0
0
1
1
0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.