invariant in the selectsort java programthe data items with indices less than or equal to outer are always sorted efficiency of the selection sort the selection sort performs the same number of comparisons as the bubble sortn*( )/ for data itemsthis is comparisons however items require fewer than swaps with items , comparisons are requiredbut fewer than swaps for large values of nthe comparison times will dominateso we would have to say that the selection sort runs in ( timejust as the bubble sort did howeverit is unquestionably faster because there are so few swaps for smaller values of nit may in fact be considerably fasterespecially if the swap times are much larger than the comparison times insertion sort in most cases the insertion sort is the best of the elementary sorts described in this it still executes in ( timebut it' about twice as fast as the bubble sort and somewhat faster than the selection sort in normal situations it' also not too complexalthough it' slightly more involved than the bubble and selection sorts it' often used as the final stage of more sophisticated sortssuch as quicksort insertion sort on the baseball players start with your baseball players lined up in random order (they wanted to play gamebut clearly there' no time for that it' easier to think about the insertion sort if we begin in the middle of the processwhen the team is half sorted partial sorting at this point there' an imaginary marker somewhere in the middle of the line (maybe you throw red -shirt on the ground in front of player the players to the left of this marker are partially sorted this means that they are sorted among themselveseach one is taller than the person to his left howeverthey aren' necessarily in their final positionsbecause they may still need to be moved when previously unsorted players are inserted between them note that partial sorting did not take place in the bubble sort and selection sort in these algorithms group of data items was completely sorted at any given timein the insertion sort group of items is only partially sorted the marked player the player where the marker iswhom we'll call the "markedplayerand all the players on her rightare as yet unsorted this is shown in figure what we're going to do is insert the marked player in the appropriate place in the (partiallysorted group howeverto do thiswe'll need to shift some of the sorted players to the right to make room to provide space for this shiftwe take the marked player out of line (in the program this data item is stored in temporary variable this is shown in