$1\mathrm{.}11$ Lab: Insertion Sort $($shift data$)$

The program in Figure $1\mathrm{.}5\mathrm{.}1$ demonstrates a variation of the Insertion Sort algorithm that is based on swapping data. Simple sorting algorithms such as Selection Sort and Bubble Sort are based on swapping data. The Insertion Sort algorithm can be implemented without swapping data: it makes room for the current element by shifting values in the array.

Read more about this implementation of the Insertion Sort algorithm: Insertion Sort: KhanAcademy

Ex$.$ If an array is being sorted using the insertion sort $($swap$)$:

$1030405060|20$

The current element to be inserted is $20$ Each swap consists of $3$ assignments $($data moves$)$

Since $20<60,$ swap $20$ and $60$: $3$ data moves

$103040502060$

Since $20<50,$ swap $20$ and $50$: $3$ data moves

$103040205060$

Since $20<40,$ swap $20$ and $40$: $3$ data moves

$103020405060$

Since $20<30,$ swap $20$ and $30$: $3$ data moves

$102030405060$

Since $20$ is not $<10,$ the swapping process stops, with a total of $12$ data moves.

Ex$.$ If an array is being sorted using the insertion sort $($shift$)$:

$1030405060|20$

The current element to be inserted is $20$

Each shift consists of $1$ assignment $($data move$)$

The first step is to copy $20$ to a temp location

temp $=20$; $//1$ data move

Since $20<60,$ shift $60$ to the right

$103040506060//1$ data move

Since $20<50,$ shift $50$ to the right

$103040505060//1$ data move

Since $20<40,$ shift $40$ to the right

$103040405060//1$ data move

Since $20<30,$ shift $30$ to the right

$103030405060//1$ data move

Since $20$ is not $<10,$ the shifting process stops, and $20$ is placed back into the array, after $10$:

$102030405060//1$ data move

A total of $6$ data moves.

Your task is to change the insertion sort by replacing swapping data with shifting data.