Question $5.$Question $5.$

Insertion$-$Sort $($ Array $A[0..n-1])$

$1.$ for integer ilarr$1ton-1$

$2.$ jlarri

$3.$ while $j>0$ and $A[j-1]>A[j]$

$4.$ swap $A[j]$ and $A[j-1]$

$5.$ jlarrj$-1$

$5($a$)$ Give an example of the worst$-$case input for "Insertion$-$Sort" at $n=8.$

Explain why it is the worst$-$case input.

$5($b$)$ Analyze the worst$-$case running time of "Insertion$-$Sort". Show your steps.

Insertion$-$Sort $($ Array $A[0..n-1])$

$1.$ for integer ilarr$1ton-1$

$2.$ jlarri

$3.$ while $j>0$ and $A[j-1]>A[j]$

$4.$ swap $A[j]$ and $A[j-1]$

$5.$ jlarrj$-1$

$5($a$)$ Give an example of the worst$-$case input for "Insertion$-$Sort" at $n=8.$

Explain why it is the worst$-$case input.

$5($b$)$ Analyze the worst$-$case running time of "Insertion$-$Sort". Show your steps.