6. [14 Points] Search & Sorting: a. (4 Points) suppose we are performing a binar

Question

6. [14 Points] Search & Sorting: a. (4 Points) suppose we are performing a binary search on a sorted array called numbers initia lized as follows: 0 1 2 3 4567 8 9 10 11 12 13 14 in [] numbers 1, 3, 5,8, 15, 18, 22, 39, 40, 42, 50, 57, 71, 73, 74); // search for the value 42 int index = binarySearch(numbers, 42); l index binary search Write the indexes of the elements that would be examined by the (the mid value returned from the search. Assume that we are using the binary search algorithm s in our algorithm's code) and write the value that would be shown in lecture section. i. What are the indexes examined? ii. What is value returned? [10 Points] Given the following array of int elements: int numbers 7, 2, 8, 4, 1, 11, 9, 5, 3, 10 b. You don't need to write the code. Just show the working Show the state of the elements after 5 passes of the outermost loop of selection sort. i. Show a trace of 2 levels deep of the merge sort algorithm. Show the splitting of the overall array, plus one level deep of the recursive calls ii.

Explanation / Answer

a. Binary search concept

#Begin

middleIndex = ( firstIndex + lastIndex )/2

In our case ,

firstIndex = 0

lastIndex = 14

middleValue = number at middle index

repeat till firstIndex <= lastIndex

if(middleValue<searchNumber)

firstIndex = middleIndex + 1;

else if(middleValue == searchNumber)

found at location middleIndex + 1;

else

lastIndex = middleIndex - 1;

middleIndex = ( firstIndex + lastIndex )/2

#End

a[I] Case 1 middleIndex = (0+14)/2 = 7

middleValue = 39 ,serachNumber = 42(If condition executed)

now firstIndex = middleIndex + 1 = 7+1=8

lastIndex = 14

Case 2 middleIndex = (8+14)/2=11

now middleValue = 57 > searchNumber(42) so else condition executed

lastIndex = middleIndex - 1 = 11-1=10

Case 3 middleIndex = (8+10)/2=9

else if condition executed ,number found at index 9.

So examined indexes are = 7 ,11 ,9

a[II] Value returned = 9

Why because int index = Binary search function

So value that is returned is always index if found else not found

In our case value is found so answer is 9.

b[I]Selection sort

#Begin

for(i=0 to n-1) //For all element traverse

{

//We will check one by one element

//Get minElement than again minElement than again minElement .....keeping one by one from starting

minIndex =i;

for(j=i+1 to n)

if(jth elem < ith ele)

minIndex = j;

swap(jth,ith) element

}

#End

Come to question

1st pass:- min 1 and 7 will swap

numbers = {1,2,8,4,7,11,9,5,3,10}

2nd pass:-2 itself min so index will not update

numbers = {1,2,8,4,7,11,9,5,3,10}

3rd pass:-swap(8,3)

numbers = {1,2,3,4,7,11,9,5,8,10}

4th pass:-swap(7,5)

numbers = {1,2,3,4,5,11,9,7,8,10}

5th pass:-

numbers = {1,2,3,4,5,7,9,11,8,10}

b[II] mergeSort

middle = (first + last)/2

mergeSort(1 to middleElement)

mergeSort(middle+1 to last element)

Merge both

numbers {7,2,8,4,1,11,9,5,3,10}

Step 1:-mergeSort(7,2,8,4,1)

mergeSort(11,9,5,3,10)

Step2:-mergeSort(7,2,8) and mergeSort(4,1)

mergeSort(11,9,5) and mergeSort(3,10)

step3:-mergeSort(7,2)&8 and 4 &1

mergeSort(11,9)&5 and 3 &10

Step4:-(7&2)&8 and 4&1

(11&9)&5 and 3&10

Step5:-Now merging after all splits

Note:- In same order need to merge

(2&7)&8 and 1&4

(9&11)&5 and 3 & 10

step6:- 2,7,8(merged in sorted order) and 1,4

5,9,11(merged in sorted order) and 1,4

step7:-1,2,4,7,8

1,4,5,9,11

step8:-all merged

1,1,2,4,4,5,7,8,9,11

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.