Selection Sort

• Algorithm
• For i<- 1 to n-1 do
• Min j <- i;
• Min x <- A[i]
• for j <- i+1 to n do
• If A[j] < min x then
• Min j <- j
• Min x <- A[j]
• A[Min j] <- A[i]
• A[i] <- Min x
• Example we have an array 40,20,60,10,50,30
• In the first pass i.e. first complete iteration of sub loop the minimum element moves to the first position.
• Array will be 10,20,60,40,50,30
• Second pass i.e. second complete iteration of sub loop the second minimum element moves to the second position.
• Array will be 10,20,60,40,50,30
• In subsequent passes the respective minimum elements will be at their correct positions. 
• 10,20,30,40,50,60
• 10,20,30,40,50,60
• 10,20,30,40,50,60
• Number of passes will be 1 less than total number of elements in the array.
• Best case is when array is already sorted.
• We will only have comparisons, no swapping.
• Sorting for first pass will have n-1 comparisons.
• Sorting for second pass will have n-2 comparisons and so on.
• We have n(n-1)/2 = O(n power 2) comparisons.
• We have O(1) as swaps complexity since there are no swaps.
• Since O(n power 2) is bigger than O(1) so the best case time complexity of selection sort is O(n power 2). 
• Inner loop runs n+(n-1)+(n-2)+(n-3) times which is an Arithemetic Progression.
• The sum of this Arithmetic Progession is n(n+1)/2 which is O(n power 2) or n square.
• This is also the time complexity of this algorithm.
• In worst case, the array is in descending order so there will be (n -1) comparisons in the first pass, and there will be one swap in the first pass.
• In the second pass, we will have (n-2) comparisons and again we will have a swap.
• Similarly, in the third pass, we will have (n-3) comparisons and one swap and so on.
• So we have n(n-1)/2 = O(n power 2) as the complexity of comparisons and O(n) complexity of swapping.
• Since O(n power 2) is bigger than O(n) so time complexity in worst case is O(n power 2).
• In average case we have O(n power 2) comparisons and O(n) snaps, so we have O(n power 2) time complexity.
• Worst case space complexity is O(1) auxiliary since it sorts in place and does not takes additional array.
• Selection sort sorts in place because it does not take extra array.
• Selection sort is not stable since it changes relative position of elements.
• Example 5,2,3,5,1 will output 1,2,3,5,5
• Here, first five comes in the last position and second five before that so elements have lost their relative position.
• Find smallest element and place in front by swapping it with first element.
• Example
• 7,8,3,1,2
• 1,8,3,7,2
• 1,2,3,7,8
• 1,2,3,7,8
• 1,2,3,7,8
• 1,2,3,7,8