So, i haven't seen a question like this before, and my answer is one i got from a bunch of different sources online. Could someone verify that it is correct and explain how to answer similar questions?
more specifically, is the last line based on a formula and how do i find the number of comparisons?
Q:Find the worst case time complexity of the selection sort algorithm for the swap operation and the comparison operation.
A:Selection sort chooses largest or smallest item in array and places the item in its correct place. Then it selects next larger or smaller item and keeps it in serial order. The process is repeated until all the elements are sorted.
In below diagram, 8 was omved from index 1 to index 4 as it was largest. then 7 was swapped and then 6 and so on until the array was sorted at last.
Swap function interchange value x and y.
Starting from index 1 to index 4, the largest value in the array will be searched. In pass 1, the largest value is 8 and was found at index 1. Therefore value at index 1 (8) will be swap with value at index last(4). There are 4 comparisons in this pass.
Number of Comparisons: 4 + 3 + 2 + 1 = 10
For array n= 5 => (n-1) + (n-2) + ….+ 2 + 1 = n(n-1)/2 = O(n2) (Comparisons) Time complexity for worst case. For swap: O(n)