Swap sort is another sorting algorithm based on exchanges. Like bubble sort, swap sort compares pairs of elements and swaps them when they are out of order, but swap sort looks at different pairs of elements than bubble sort does. On pass i of swap sort, the element in position i of the array is compared with the elements in all positions to the right of position i$,$ and pairs of elements are swapped as needed. At the end of pass i$,$ the element in position i is where it belongs in the sorted array.

For example, let$$s say that we have the following initial array:

$\{15,8,20,5,12\}$

On pass $0,$ swap sort compares the element in position $0$ with the elements in positions $1$ through n $-1,$ where n is the number of elements in the array. First, $15$ is compared to $8,$ and because $8$ is less than $15,$ the two elements are swapped:

$\{8,15,20,5,12\}$

Next, $8($which is now in position $0)$ is compared to $20,$ and no swap occurs because $8$ is already smaller than $20.$ Then $8$ is compared with $5,$ and the two elements are swapped:

$\{5,15,20,8,12\}$

Finally, $5$ is compared to $12,$ and no swap occurs because $5$ is already smaller than $12.$ At this point, pass $0$ is complete, and the element in position $0($the $5)$ is where it belongs in the sorted array.

On pass $1,$ swap sort compares the element in position $1$ with the elements in positions $2$ through $($n $-1)$ and performs swaps when needed. The process continues for passes $2$ through $($n $-2),$ at which point the array is fully sorted.

What is the best case for this algorithm? In this best case, what is the big$-$O expression for the number of comparisons that it performs? For the number of moves? What is its overall time efficiency? Explain your answers briefly.

What is the worst case for this algorithm? In this worst case, what is the big$-$O expression for the number of comparisons? For the number of moves? What is its overall time efficiency? Explain your answers briefly.