Problem 120 Selection Sort
Back to Problem Solutions forum
Hello you all, I don't really have a problem per say, but more like I don't understand the question.
""""""""""""""""""""""""""
You are to implement the algorithm described above and print out the index of selected maximum at each pass.
Input data will contain N - the size of array - in the first line. Next line will contain the array itself (all elements will be different). Answer should contain indices of the maximums at each pass (N-1 values).
Example:
input data:
6
31 41 59 26 53 58
answer: 2 2 2 1 0
""""""""""""""""""""""""""
That above is the example. What is don't understand is in the example. First of all there 6 seperate numbers in the example and 5 answer, what's with that. And then, if I manually do the question, max no. '59' is on the index 2 and got shifted to the back. And there a 2 in the answer, okay, nice.
Then the new list becomes [31 41 26 53 58]. Now the max no. is 58 at index 4, but in the answer it's again 2.
new list = [31 41 26 53] again in this, the max no. would be 53 at index 3 and theres no 3 in the index.
So, am I not understanding something? If yes, please explain. I'm kinda stuck on this one for like an hour.
Hi there!
It seems to be a little confusion about one of the steps:
Then the new list becomes [31 41 26 53 58]
Not so! You do shifting the "tail" of the array to fill in the hole. But shifting is a costly operation (in this case it
will make algorithm as slow as O(N^3) instead of O(N^2)). That is why we fill in the gap in easier way:
swap it with the last element in the sub-array (i.e. with position N-2)
E.g. in this example we proceed like this:
[31 41 59 26 53 58]
^ ^
\_______/
[31 41 58 26 53] 59
^ ^
\____/
[31 41 53 26] 58 59
^ ^
\_/
[31 41 26] 53 58 59
^ ^
\_/
[31 26] 41 53 58 59
^ ^
\_/
Hope this helps!
Ahhh, now I understand. Thanks for the explanation, mate.