Sign up for FREE

Merge Sort Work Sheet

Last updated about 2 years ago

8 questions

1

1

1

1

Question 1

1.

Complete the following method linearSearch which should return the location of findVal in the array list. If findVal does not exist, linearSearch will return -1.
int linearSearch( double[] list, double findVal ) {
//Code goes here.
}

Question 2

2.

2. Complete the following method numOccurences which should return the # of occurrences of findVal in list. If findVal = 7 and 7 occurs 10 times in the array list, then the method should return 10.
int numOccurrences( double[] list, double findVal){
//Code goes here.
}

Question 3

3.

Question 4

4.

public void sort2(Comparable[] list )
{
for (int i=1; i< list.length; ++i)
{
int bot=0, top=i-1;
while (bot<=top)
{
int mid=(bot+top)/2;
if (list[mid].compareTo(list[i])<0)
bot=mid+1;
else top=mid-1;
}
Comparable temp=list[i];
for (int j=i; j>bot; --j)
list[j]=list[j-1];
list[bot]=temp;
}
}

Integer[] list = {3,15,61,11,7,9,2};

Show the contents of list after 5 passes of sort2.

1

1

1

1

public void sort1( Comparable[] list )
{
    int i, j, min;
    for( i=0; i<list.length-1; i++)
    {
        min = i;
        for(j=i+1; j<list.length; j++)
        {
            if(list[min].compareTo(list[j]) > 0)
                min = j;
         }
         if( min != i)
         {
              Comparable temp = list[min];
              list[min] = list[i];
              list[i] = temp;
          }
     }    
}

Integer[] list  = {3,15,61,11,7,9,2};

Show the contents of list after 4 passes of sort1.

Complete the following method binarySearch.   Fill in each blank below.
int binarySearch(int [] stuff, int val )
{
    int bot= 0, top = stuff.length-1;
    while(bot<=top)
    {
        int middle =  __________________________
        if (stuff[middle] == val)  return middle;
        else
            if (stuff[middle] > val)
                 top = _____________________
            else
                 bot = _____________________
}
return -1;
}
 Write the  binarySearch using recursion.  

public static int binarySearch(int[] stuff, int item, int bot, int top)
{
    //Code goes here.
}

Question 5

5.

middle = __________________________

Question 6

6.

top = ____________________________

Question 7

7.

bot = __________________________

Question 8

8.

// Code goes here.