Number of comparisons in Straight Selection sort

31,519

Solution 1

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".

Solution 2

(n*(n-1))/2 gives no. of comparisons for selection sort

Share:
31,519

Related videos on Youtube

Utkal Sinha
Author by

Utkal Sinha

My areas of interest includes Cloud computing Machine learning Computer networking Computer vision I am also passionate about chess and enjoy socializing.

Updated on June 21, 2021

Comments

  • Utkal Sinha
    Utkal Sinha over 2 years

    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.

    • Bernhard Barker
      Bernhard Barker almost 10 years
    • Utkal Sinha
      Utkal Sinha almost 10 years
      @Dukeling I have seen that post before posting my question here. None of the answers there were able to explain how the answer to my above question is 20 and not 10. If you have a proper explanation to it then please do let me know.
  • Alexandre Cartapanis
    Alexandre Cartapanis over 4 years
    Needs more explication

Related