Problem:
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[j]?
(true or false)
|
A[0]
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
|
|
....
|
|
|
|
|
values of A[j] at the end of each iteration
|
(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]
Additional Information:
This question is from Computer Science as well as it explains about the algorithm insertionSort.
Total Word Limit: 251 Words