# How The Algorithm insertionSort Operates

Question

The insertion sort algorithm is stated below. Operation of insertion sort can be described as follows. The list at any moment is divided into two parts: sorted and unsorted. In each pass of the algorithm, the first element of the unsorted sub-list is moved to the sorted sub-list by inserting it at the appropriate place.

(i) Show how algorithm insertionSort operates by tracing it on the list 32, 15, 58, 7, 24, 30.
Fill in the following table.

 i j tmp j≥0 ? (true or false) tmp

(ii) Give an example of an array that makes the insertion sort exhibit its worst behavior.

(iii) Count how many comparisons tmp < A[j] are done by the algorithm in the worst case (for an arbitrary n) and state its complexity in terms of Big-Oh.

ALGORITHM insertionSort(A[0..n – 1])
//The algorithm sorts a given array by insertion sort
//Input: an array A[0..n – 1] of n numbers
//Output: array A[0..n – 1] sorted in ascending order
for i ← 1 to n – 1 do
tmp ← A[i]
j ← i – 1
while (j≥0 and tmp < A[j]) do
A[j + 1] ← A[j]
j ← j – 1
A[j + 1] ← tmp
output A[0..n – 1]

Summary

The question belongs to Computer Science and it discusses about the algorithm insertionSort.

Total Word Count 251

• Rasha

this is a very good website

• maani

I have 50 questions for the same test your page is showing only 28

• joeanne

• joeanne

hi can anyone help or guide me to my assignments. thanks

• Monik

• Cristina

This solution is perfect ...thanks

• Janete

Hello Allison,I love the 2nd image that you did! I also, had never heard of SumoPaint, is something that I will have to exolpre a bit! I understand completely the 52 (or so) youtube videos that you probably watched. Sometimes they have what you want, sometimes they don't! However, it is always satisfying when you are able to produce something that you have taught yourself. Great job!Debra 0 likes

• Sandeep

Perfect bank of solution.

• Oxana

great !

• Paul Brandon-Fritzius

thanks for the quick response. the solution looks good. :)

• tina Johnson

thnx for the answer. it was perfect. just the way i wanted it.

• Giuseppe

works fine.