Number of comparisons in Straight Selection sort
algorithm, sorting
Solution
10 should be the correct answer.
From Wikipedia:
Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all `n` elements (this takes `n − 1` comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining `n − 1` elements and so on, for `(n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n^2)` comparisons.
So, for 5 elements, it'd be `5*4/2 = 20/2 = 10` (note "none of the loops depend on the data in the array", so the fact that it's in descending order doesn't play a role in the number of comparisons).
The difference between what I'd assume are straight and exchange selection sort don't affect the number of comparisons.
It would make sense that exchange exchanges (swaps) elements and straight shifts elements up (or uses a data structure that doesn't require shifting up, such as a linked list). Note that we only do comparisons to find the element we want, there are no (element) comparisons involved with either swapping, shifting or linked-list insertion.
Wikipedia uses exchanging as the default algorithm and lists the alternative under "Variants".
Problem
I found this question in a Pearson book. ``` How many comparisons are needed to sort an array of length 5 (whose element are already in opposite order) using straight selection sort? a. 5 b. 20 c. 4 d. 10 ``` It is given that the correct answer is b. 20 But I think it would be d. 10 Please explain how the answer is 20. I also Googled for straight selection sort but I am getting only results for Selection sort. I also found the term exchange selection sort. Till now, I have only heard about Selection sort only, so please give some views on the difference between Exchange and Straight selection sort. Thanks in advance.