Question $9$

$[10$ marks$]$

Given that Figure $9$ illustrates how Insertion$-$Sort works, write down its algorithm on the right$-$hand side $(4$ marks$)$ using the Selection$-$Sort algorithm on the left side. Determine the time complexity of the best and worst cases for Selection$-$Sort and Insertion$-$Sort $(4$ marks$).$ Finally, determine which of these two sorting algorithms is more efficient $(2$ marks$).$ Figure $9.$ How Insertion$-$Sort works.

Hint: You may consider the run time frequency of each line and then estimate the final time complexity.