When you look closely at the Insertion Sort you will notice that the insertion o
ID: 3763125 • Letter: W
Question
When you look closely at the Insertion Sort you will notice that the insertion of the next element into the already sorted list basically does a sequential search to determine where the element should be inserted. Consider a variation of the standard Insertion Sort algorithm that does a binary search on the already sorted part of the list to determine the location where the element should be inserted. Assuming that the keys are unique, note that a standard binary search would always return a failure. Therefore assume that you are using a slightly modified version of binary search that returns the location where the key to be inserted belongs. What is the average case cost for the number of comparisons for this new version of Insertion Sort?
Explanation / Answer
Answer:
The way the question is explained is nothing but the Binary Insertion Sort.
The algorithm by modifying the inserting the element into the correct position by binary searching the element with in the sorted array is known as Binary Insertion Sort.
Binary Insertion Sort Algorithm:
First Consider the InsertionSort algorithm as follows:
algorithm insertionSort(A[], n):
i, location, j, k selected
for I = 1 to n do
j = i – 1
selected = A[i]
//to find the location where selected should be inserted
location = binarySearchAlgo(A, selected, 0, j);
while j >= location do
A[j+1] = A[j]
j—
end while
a[j+1]=selected
end for
end algorithm
Now consider the Binary Search algorithm as follows:
algorithm binarySearchAlgo (A[], item, low, high):
if high <= low then
if item >a[low] then
return low+1
else
return low
end if
end if
mid = (low + high)/2
if item == a[mid] then
return mid+1
end if
if item > a[mid] then
return binarySearchAlgo(A, item, mid+1, high)
end if
return binarySearchAlgo(A, item, low, mid-1)
end algorithm
The average cost of the algorithms takes at most O (n2).
The average cost takes O (n2) because of the swapping in the insertion sort,
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.