Question

Use the insertion sort to sort the list in Exercise 35, showing the list obtained at each step.

Short answer

The sorted list using insertion sort is a,b,d,f,k,m.

Step-by-step solution

Step 1

We have to sort the list d,f,k,m,a,b using insertion sort Begin with comparing first and second letter in the list d,f,k,m,a,b

No interchange required

Now the list becomes d,f,k,m,a,b.

Step 2

Now we will compare third letter with first and second letter (comparing ‘k’ with d,f)

no interchange required

Now the list becomes d,f,k,m,a,b.

Step 3

Now we will compare fourth letter with first, second, third letters (comparing ‘m’ with d,f,k) no interchange required.

Now the list becomes d,f,k,m,a,b.

Step 4

Now we will compare fifth letter with first, second, third, fourth letters (comparing ‘a’ with d,f,k,m) So ‘a’ will be inserted before ‘d’.

Now the list becomes a,d,f,k,m,b.

Step 4

Now we will compare fifth letter with first, second, third, fourth letters (comparing ‘b’ with a,d,f,k,m) So ‘b’ will be inserted before ‘d’.

Now the list becomes a,b,d,f,k,m,.

Final answer                                                                                                                        

The sorted list using insertion sort is a,b,d,f,k,m.