number of steps for of insertion sort are both proportional to and hence the average and worst case time complexities are both ( selection sort selection sort is (not surprisinglya form of selection sorting it first finds the smallest item and puts it into [ by exchanging it with whichever item is in that position already then it finds the second-smallest item and exchanges it with the item in [ it continues this way until the whole array is sorted more generallyat the ith stageselection sort finds the ith-smallest item and swaps it with the item in [ - obviously there is no need to check for the ith-smallest item in the first elements of the array for the example starting array selection sort first finds the smallest item in the whole arraywhich is [ ]= and swaps this value with that in [ giving thenfor the second stepit finds the smallest item in the reduced array [ ], [ ], [ ]that is [ ]= and swaps that into [ ]giving finallyit finds the smallest of the reduced array [ ], [ ]that is [ ]= and swaps that into [ ]or recognizes that swap is not neededgiving the general algorithm for selection sort can be writtenfor - + for + +if [ja[kk swap [iand [kthe outer loop goes over the first positions to be filledand the inner loop goes through the currently unsorted portion to find the next smallest item to fill the next position note thatunlike with bubble sort and insertion sortthere is exactly one swap for each iteration of the outer loopthe time complexity is again the number of comparisons carried out the outer loop is carried out times in the inner loopwhich is carried out ( timesone comparison occurs hence the total number of comparisons isn- - = = + - ( ii= ( ( therefore the number of comparisons for selection sort is proportional to in the worst case as well as in the average caseand hence the average and worst case time complexities are both ( note that bubblesortinsertion sort and selection sort all involve two nested for loops over (nitemsso it is easy to see that their overall complexities will be ( without having to compute the exact number of comparisons