determining bubble sort' number of comparisons is easy regardless of the arrangement of the values in the arraythe number of comparisons made by the inner for loop is always ileading to total cost of th( = bubble sort' running time is roughly the same in the bestaverageand worst cases the number of swaps required depends on how often value is less than the one immediately preceding it in the array we can expect this to occur for about half the comparisons in the average caseleading to th( for the expected number of swaps the actual number of swaps performed by bubble sort will be identical to that performed by insertion sort selection sort consider again the problem of sorting pile of phone bills for the past year another intuitive approach might be to look through the pile until you find the bill for januaryand pull that out then look through the remaining pile until you find the bill for februaryand add that behind january proceed through the ever-shrinking pile of bills to select the next one in order until you are done this is the inspiration for our last th( sortcalled selection sort the ith pass of selection sort "selectsthe ith smallest key in the arrayplacing that record into position in other wordsselection sort first finds the smallest key in an unsorted listthen the second smallestand so on its unique feature is that there are few record swaps to find the next smallest key value requires searching through the entire unsorted portion of the arraybut only one swap is required to put the record in place thusthe total number of swaps required will be (we get the last record in place "for free"figure illustrates selection sort below is java implementation static void sort( [afor (int = < length- ++/select 'th record int lowindex /remember its index for (int = length- >ij--/find the least value if ( [jcompareto( [lowindex] lowindex /put it in place dsutil swap(ailowindex)selection sort is essentially bubble sortexcept that rather than repeatedly swapping adjacent values to get the next smallest record into placewe instead