Question
Counting Sort Operation Question Someone PLEASE explain a certain facet of counting sort to me! No code, just plain English. I know that you need
Counting Sort Operation Question
Someone PLEASE explain a certain facet of counting sort to me! No code, just plain English.
I know that you need three arrays: A, your original. C, your temporary storage array with the counts of each element (and later you add consecutive integers in C together); and finally B, your sorted array.
However, I am having a very difficult time figuring out how you are supposed to decide what indices in B to fill and when. Let me give you an example.
Given an array A with [6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2] that goes from i = 1 to i = 11, use counting sort and display this in array B. Sounds simple enough right? However I CANNOT figure out the pattern for realizing which indices to go on when I'm filling Array B.
Here is my array C before summing the integers: C = [2, 2, 2, 2, 1, 0, 2] going from j = 0 to j = 6. Then, after I add the integers, C = [2, 4, 6, 8, 9, 9, 11].
Now here's the tricky part. Array B. Here are the first few steps:
array B:
indices: [1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11]
values: [ | | | | | 2 | | | | | ]
You can see that element 2 has been placed at indice 6 within the new Array B. Now, array C looks like this: C = [2, 4, 5, 8, 9, 9, 11]. As you can see, 6 was decremented to represent this new feature.
Now for the next step:
indices: [1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11]
values: [ | | | | | 2 | | 3 | | | ]
You can see that element 3 has now been placed at index 8. Array C is now C = [2, 4, 5, 7, 9, 9, 11]; the 8 was decremented.
This is where I'm getting confused. HOW are we choosing our B-placements and values here??? I don't understand how we can go from index 6 to index 8 and why we are doing it! The final step I'm showing:
indices: [1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11]
values: [ | | | 1 | | 2 | | 3 | | | ]
As you can see, value 1 was placed at index 4. Array C is now C = [2, 3, 5, 7, 9, 9, 10].
So I'm extremely confused and I just want to learn. How are they choosing B-indexes and values here? I know it's not random. I keep doing it out of order and trying different patterns but NONE of them are matching up with the operations shown here. How do I decide where to go to fill Array B?
I need an answer that specifically answers this question: How do I decide to fill Array B, in THIS situation with this specific type of operation? What is the pattern that I am missing?
I don't know why I am not figuring this out but any help would be sincerely appreciated.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started