Use the Binary Search Algorithm to determine whether the num

Use the Binary Search Algorithm to determine whether the number 17 appears in the sequence s: 3, 6, 7, 8, 15, 17, 19, 23, 24. Give a step description of what the algorithm does in this case. Use the Binary Search Algorithm to determine whether the number 11 appears in the sequence s: 2, 4, 5, 7, 9, 10, 12, 14, 15, 16, 19, 23. Give a table that presents a step by step Give a step description of what the algorithm does in this case. Use the bubble sort Algorithm on the sequence s: 11, 9, 10, 8 so that the terms are recorded from smallest to largest. Give a table that presents a step by step description of what the algorithm does in this case. Use the bubble sort Algorithm on the sequence s: 3, 9, 7, 6, 5 so that the terms are reordered from smallest to largest. Give a table that presents a step by step description of what the algorithm does in this case. Write a new Bubble sort Algorithm that sorts the terms of a sequence s: a_1, a_2, ..., a_n of n numbers so that the terms of s are reordered from largest to smallest. Sort the list s: 6, 4, 2, 1, 3, 5 by the insertion sort Algorithm. Give a diagram that presents a step by step description of what the algorithm does in this case. Write a new Insertion Sort Algorithm that sorts the terms of a sequence s: a_1, a_2, ..., a_n of n numbers so that the of s are reordered from largest to smallest. Indicate how the two sorted lists s_1: 1, 3, 4, 7, 8, 9 and s_2: 2, 5, 6 are merged into a single sorted list by the Merge Sort Algorithm.

Solution

1) Binary Search Algorithm:

first = 0

last = (Length of list -1 ) => 9-1 = 8

mid = (first+last)/2 => (0+8)/2 => 4

We search whether 17 exists at 4th position of the array.

However 17 exists at position 5th of the array and at 4th position we have element 15.

Therefore, rechanging initial and last limit of the array , now

first=(mid+1) => 4+1 -> 5 (Since element 17 is greater than element 15 , we observed that it would exist in 2nd half of the array)

last=8 (same as before)

mid=(5+8)/2 => 6.5 = 6(integer value)

We will search element 17 at mid point first again.

But element at position 6 of the array is 19. (which is greater than element 17).

Again we resize the array (now as element 19 is greater than element 17 which is to be searched) , therefore we know that 17 would exists in 1st half of this new array with mid element 19.

first=5 (same as previous case)

last=(mid-1)=>(6-1)=5

mid=(5+5)/2 => 5

Searching element at position 5 => We have element 17 at position 5 of the array.

Hence found.

2)

Sequence : 2 , 4 , 5 , 7 , 9 , 10 , 12 , 14 , 15 , 16 , 19 , 23

first = 0

last = (Length of list -1 ) => (12-1) => 11

mid = (first+last)/2 => (0+11)/2 => 5.5 = 5 (integer value)

Now, searching for number 11 at mid point first. But at mid point (ie. element 5th of array) we have number 10.

Thus, we know that if 11 would exist in the sequence it would exist in the 2nd half of this array (ie. numbers after the mid point)

Iteration 2 :

first= mid+1 = 5+1 = 6

last= 11 (same as before)

mid=(6+11)/2 => 8.5 = 8 (integer value)

Search for element 11 at mid point first . But at mid point (ie. element 8th of array) we have number 15.

Thus, we know that if 11 would exist in the sequence it would exist in the 1st half of this array (ie. numbers before the mid point).

Iteration 3 :

first= 6 (same as before)

last= mid-1 = 8-1 = 7

mid=(6+7)/2 => 6.5 = 6 (integer value)

Search for element 11 at mid point first . But at mid point (ie. element 6th of array) we have number 12.

This was the shortest array of the complete sequence. We cannot subdivide it further.

Hence proved, we don\'t have element 11 in the sequence.

3) Bubble sort :

Sequence : 11 , 9 , 10 , 8

Iteration 1-a : Start with the first 2 elements (ie. 11 and 9)

check if 11 > 9 , if yes swap the 2 values

Result after Iteration1-a : 9 , 11 , 10 , 8

Iteration 1-b : Check for the next 2 elements (ie. 2nd and 3rd element)

check if 11 > 10 , if yes swap the 2 values

Result after Iteration1-b : 9 , 10 , 11 , 8

Iteration 1-c : Check for the next 2 elements (ie. 3rd and 4th element)

check if 11 > 8 , if yes swap the 2 values

Result after Iteration1-c : 9 , 10 , 8 , 11

Iteration 2-a : Check for the first 2 elements (ie. 1st and 2nd element)

check if 9 > 10 , if yes swap the 2 values

Result after Iteration2-a : 9 , 10 , 8 , 11

Iteration 2-b : Check for the next 2 elements (ie. 2nd and 3rd element)

check if 10 > 8 , if yes swap the 2 values

Result after Iteration2-b : 9 , 8 , 10 , 11

Iteration 2-c : Check for the next 2 elements (ie. 3rd and 4th element)

check if 10 > 11 , if yes swap the 2 values , else not

Result after Iteration2-b : 9 , 8 , 10 , 11

Iteration 3-a : Check for the first 2 elements (ie. 1st and 2nd element)

check if 9 > 8 , if yes swap the 2 values

Result after Iteration3-a  : 8 , 9 , 10 , 11

List is sorted now.

4)

Bubble sort :

Sequence : 3 , 9 , 7 , 6 , 5

Iteration 1-a : Start with the first 2 elements (ie. 1st and 2nd element)

check if 3 > 9 , if yes swap the 2 values

Result after Iteration1-a : 3 , 9 , 7 , 6 , 5

Iteration 1-b : Check for the next 2 elements (ie. 2nd and 3rd element)

check if 9 > 7 , if yes swap the 2 values

Result after Iteration1-b : 3 , 7 , 9 , 6 , 5

Iteration 1-c : Check for the next 2 elements (ie. 3rd and 4th element)

check if 9 > 6 , if yes swap the 2 values

Result after Iteration1-c : 3 , 7 , 6 , 9 , 5

Iteration 1-d : Check for the next 2 elements (ie. 4th and 5th element)

check if 9 > 5 , if yes swap the 2 values

Result after Iteration1-d :  3 , 7 , 6 , 5 , 9

Iteration 2-a : Start with the first 2 elements (ie. 1st and 2nd element)

check if 3 > 7 , if yes swap the 2 values

Result after Iteration2-a : 3 , 7 , 6 , 5 , 9

Iteration 2-b : Check for the next 2 elements (ie. 2nd and 3rd element)

check if 7 > 6 , if yes swap the 2 values

Result after Iteration2-b : 3 , 6 , 7 , 5 , 9

Iteration 2-c : Check for the next 2 elements (ie. 3rd and 4th element)

check if 7 > 5 , if yes swap the 2 values

Result after Iteration2-c :  3 , 6 , 5 , 7 , 9

Iteration 2-d : Check for the next 2 elements (ie. 4th and 5th element)

check if 7 > 9 , if yes swap the 2 values

Result after Iteration2-d :  3 , 6 , 5 , 7 , 9

Iteration 3-a : Start with the first 2 elements (ie. 1st and 2nd element)

check if 3 > 6 , if yes swap the 2 values

Result after Iteration3-a : 3 , 6 , 5 , 7 , 9

Iteration 3-b : Check for the next 2 elements (ie. 2nd and 3rd element)

check if 6 > 5 , if yes swap the 2 values

Result after Iteration3-b : 3 , 5 , 6 , 7 , 9

Sequence is now sorted.