The selection sort works by dividing the input array into a sorted sublist S $($which is initially empty$)$ followed by an unsorted sublist U$.$ During each pass through of U$,$ the smallest element in U is identified and swapped with the first element of U$.$ The length of S is increased by one and the length of U decreased by one. As an example $($sorted elements bolded$)$:

$2330952625$ Input Array

$2330952625$ No Swap

$2325952630$ Swap $25$ and $30$

$2325269530$ Swap $26$ and $95$

$2325263095$ Swap $30$ and $95$

$2325263095$ No Swap

$(25$ points$)$ Give pseudocode implementing the selection sort.

$(10$ points$)$ Give a big$-$O bound on the worst$-$case runtime of your algorithm.