recall the priorityqueuesort scheme introduced in section we are given an unsorted sequence containing elementswhich we sort using priority queue in two phases in phase we insert all the elements into and in phase we repeatedly remove the elements from using the removemin(method selection-sort if we implement with an unsorted listthen phase of priorityqueuesort takes (ntimefor we can insert each element in ( time in phase the running time of each removemin operation is proportional to the size of thusthe bottleneck computation is the repeated "selectionof the minimum element in phase for this reasonthis algorithm is better known as selectionsort (see figure as noted abovethe bottleneck is in phase where we repeatedly remove an entry with smallest key from the priority queue the size of starts at and incrementally decreases with each removemin until it becomes thusthe first removemin operation takes time ( )the second one takes time ( )and so onuntil the last (nthoperation takes time ( thereforethe total time needed for the second phase is by proposition we have ( )as does the entire selection-sort algorithm thusphase takes time figure execution of selection-sort on sequence ( , , , , , ,