Insertion sort

Question 1

What is the structured English for insertion sort?

Answer 1

• Repeat the following for each item in the list, excluding the first
• Remember the current item as the key
• Move every item before the key that is bigger than it forward
• Place the key item before these larger items

Question 2

How to write an insertion sort in pseudocode?

Answer 2

for i = 1 to A.length – 1
key = A[i]
j = i - 1
while j >= 0 AND A[j] > key
A[j + 1] = A[j]
j–
endWhile
A[j + 1] = key
next i

Question 3

Where does an insertion sort start?

Answer 3

At the second index, since the first is already sorted.

Question 4

What is the difference between an insertion sort and a bubble sort?

Answer 4

The algorithm shifts values along. It does not swap values. (Bubble sort swaps, insertion sort shifts).

Question 5

What are advantages of an insertion sort?

Answer 5

• Easy to implement
• Good for small data sets that are almost sorted
• Insertion sort generally performs quicker than bubble sort and is therefore preferable.

Question 6

What is a disadvantage of an insertion sort?

Answer 6

It does not scale well so it’s not good for large data sets.

Question 7

What is the worst case scenario for an insertion sort? (ascending)

Answer 7

Worst case scenario for ascending sort is when the values are in descending order

Question 8

What is the best case scenario for an insertion sort?

Answer 8

Best case scenario is the data is already sorted