on of insertion sort is known as binary insertion .The following sort. It uses b
ID: 3741196 • Letter: O
Question
on of insertion sort is known as binary insertion .The following sort. It uses binary search to find the kn binary insertion sora, b: INTEGER is search to find the position of the ne xt insertion local i.J.pos: INTEGER r like entry type do from i := a + 1 until i > b loop x:= entries.item(i): pos: binary search(a, i-1,x.key): from j:-i - 1 until j-pos loop entries put(entries.item(j).j +1); end entries put(x,j+1); i:si+l end end a Analyze binary insertion sornl.m), using one compurison berwcon ries nu(entries.item(),j+ I) as keys as the characteristic operationExplanation / Answer
ANS:-
Lets understand Binary Search First:
Given the following dataset of 9 items in sorted order, find the value 8:
[11 12 13 14 15 16 17 18 19]
The first step is to check the midpoint (there are 9 elements, so the midpoint would be (9+1)/2 which is the 5th element):
[11 12 13 14 15 16 17 18 19]
Well, 15 is not 18 so we're not done yet. Is 18 less than 15? No. Is 18 greater than 15? Yes. So we know that the value we seek is in the second half of the array (if it's there). We are now left with:
[16 17 18 19]
Oops. 4 does not have a midpoint, so we round off any way we want to (it really doesn't matter). (4+1)/2 = 2.5, so for the sake of argument lets just drop the decimal and check the 2nd element (this is how integer math works anyway, so it's simpler):
[16 17 18 19]
Well, 17 is not 18 so we're not done yet. Is 18 less than 17? No. Is 18 greater than 17? Yes. So we know that the value we seek is in the second half of the array (if it's there). We are now left with:
[18 19]
Again we find the midpoint, which in this case is 1.
[18 19]
Does 18 equal 18? Yes! We're done!
Since we have understood now how a binary search works now lets jump in to understand the binary insertion sort. Insertion sort in which the proper location for the next item is found with a binary search.
void BinaryInsertionSort (int a[], int n)
{
int pos, i, j;
int x;
for (i = 1; i < n; i++) { // scan each element from the array
pos = BinarySearch (a, 0, i, a[i]); // find position using a binary search
if (pos < i) { // if the curr pos is less than i
x = a[i]; // temporary var
for (j = i - 1; j >= pos; j--) // replace till the positions
a[j + 1] = a[j];
a[pos] = x; // insert the element in its correct location
}
}
}
Binary insertion sort Beefits
sequential search --> binary search
reduce # of comparisons,and # of moves unchanged
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.