StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q47E

Expert-verifiedFound in: Page 203

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Show all the steps used by the binary insertion sort to sort the list 3, 2, 4, 5, 1, 6.**

By using the binary insertion sort, the given array 3,2,4,5,1,6 became 1,2,3,4,5,6 .

- Binary insertion sort first compares the second element with the first element and places the second element as appropriate.
- On each subsequent pass from now on, the current element is compared with the middle of the already sorted array and determines in which subinterval does the element lie.
- This is done repeatedly until we have obtained the position at which the element should be ideally inserted and the element inserted at the correct place.
- The given array is 3,2,4,5,1,6 .

First, compare the 2 with the first element of our array, 3 .

Since 3 > 2 so inserted 2 before 3 .

Then the array become $2,3,4,5,1,6$ .

Similarly, compare 4 with the first element of our array, 2 .

Since so insert after 2.

Now, compare 4 with the second element of our array, 3 .

Since 4 > 3 so insert 4 after 3 .

Then the array become 2,3,4,5,1,6 .

Now, compare 5 with the second element of our array (as this element is the half-way point), 3 .

Since 5 > 3 so insert 5 after 3 .

Again, compare 5 with the third element of our array, 4 .

Since 5 > 4 so inserted 5 after 4.

Then the array become 2,3,4,5,1,6 .

Now,** **compare 1 with the second element of our array (as this element is the half-way point) , 3 .

Since 1 < 3 then should be inserted before 3 .

Again, compare 1 with the first element of our array 2 .

Since 1 < 2 so should be inserted before 2 .

Then the array become 1,2,3,4,5,6 .

Now, compare 6 with the third element of our array (as this element is now the half-way point), 3 .

Since 6 > 3 so inserted 6 after 3 .

Again, compare 6 with the fourth element of our array, 4 .

Since 6 > 4 so inserted 6 after 4 .

Again, compare 6 with the fifth element of our array, 5 .

Since 6 > 5 so inserted 6 after 5 .

Then the array become 1,2,3,4,5,6 .

Hence, the array become 1,2,3,4,5,6 .

94% of StudySmarter users get better grades.

Sign up for free