Merge Sort Work Sheet

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.
}

1

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.
}

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.

1

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.

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.
}

1

middle = __________________________

1

top = ____________________________

1

bot = __________________________

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.}

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.}

middle = __________________________

top = ____________________________

bot = __________________________

// Code goes here.

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.
}

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.
}