MergeSort

[Joe Grimp]

I have to modify a MergeSort method to sort a list of Comparable objects.
I also have to modify the code to determine how many comparisons of items occur during the sorting process by incrementing a class level variable comparisons and then use the program to confirm the theoretical predictions of performance for Mergesort.

Here is the MergeSort Method -

  public class MergeSort_Q3
 
{public static void main(String[] args)
{
int[] grades = {89, 94, 69, 80, 97, 85, 73, 91, 77, 93};
System.out.println("Unsorted values");
output(grades);
mergeSort(grades);
System.out.println("Sorted values");
output(grades);
}
 
public static void mergeSort(int[] L)
{ 
     int[] leftList, rightList;
 
     if(L.length > 1)
                      {
   int left = L.length/2;
   int right = L.length-left;
  leftList = new int[left];
   rightList = new int[right];
 

   for(int i = 0; i< left; i++)  leftList[i] = L[i];
   
   for(int i = 0; i< right; i++) rightList[i] = L[i+left];
 
   mergeSort(leftList);
   mergeSort(rightList);
 

int indexLeft = 0;
int indexRight = 0;
int indexOutput = 0;
while (indexLeft < left && indexRight < right)
{
if(leftList[indexLeft] < rightList[indexRight])
{
L[indexOutput] = leftList[indexLeft];
indexLeft++;
}else{
L[indexOutput] = rightList[indexRight];
indexRight++;
}
indexOutput++;
}

while(indexLeft < left)
{
L[indexOutput] = leftList[indexLeft];
indexLeft++;
indexOutput++;
}
 
while(indexRight < right)
{
L[indexOutput] = rightList[indexRight];
indexRight++;
indexOutput++;
}
     }
 

}
 


public static void output(int[] data)
{
for(int i=0; i<data.length; i++)
System.out.print(data[i] + " ");

System.out.println();
} // output

}  

I'm not sure of where to begin with this problem, and any help would be appreciated. Thanks.

[Jesper de Jong]

I hope this helps to get you started:

Somewhere in your code above you are comparing two objects to find out which one is "smaller" than the other one. You want to count the number of comparisons. There is exactly 1 line in the mergeSort(...) method where the comparison is done, so there you simply have to increment the counter.

Look hard, make sure you understand the code and find the line where the comparison is done.

[Joe Grimp]

I have decided to make the list of comparible objects Account objects -

   Account[] bank = new Account[5];
double totalBal, smallestBal, largestBal;

bank[0] = new Account("Ted Murphy", 72354, 102.56);   
bank[1] = new Account("John Smith", 69713, 40.00);
bank[2] = new Account("Ted Murphy", 72354, 102.56);
bank[3] = new Account("Marcus O'Hare", 71234, 500.0);
bank[4] = new Account("Margaret Jones", 89761, 475.0); 

Where should i put my compareTo method in my code now?? And what should i be changing in following line of code to make the comparison work?? -

  if(leftList[indexLeft] < rightList[indexRight])  

Thanks.

[Jesper de Jong]

Good, you're on the right track. I see you've found the line of code where the comparison is done already.

I guess your class Account implements interface Comparable, so the implementation of the compareTo method is present in the Account class.

Your mergeSort() method now takes an array of ints:

public static void mergeSort(int[] L)

If you want it to work on objects that implement the Comparable interface, you'll have to change it to take an array of Comparable objects:

public static void mergeSort(Comparable[] L)

Ofcourse you'll have to change other parts of the mergeSort() method also to make it work with an array of Comparable objects instead of an int array.

Instead of comparing two ints with the < operator, you call the compareTo() method to compare two Comparable objects. The API documentation of the compareTo() method in the Comparable interface describes the possible return values: < 0 if the object you're calling the method on is less than the object you're comparing it with, = 0 if they are equal, > 0 if the object you're calling the method on is greater than the object you're comparing it with.

[Joe Grimp]

Ok, i have completed this piece of code and it compiles and runs -

public class CW_Q1
{
 
static int comparisons;
 
public static void main(String[] args)
{
Account1[] bank = new Account1[5];
double totalBal, smallestBal, largestBal;

bank[0] = new Account1("Ted Murphy", 72354, 102.56);   
bank[1] = new Account1("John Smith", 69713, 40.00);
bank[2] = new Account1("Ted Murphy", 72354, 102.56);
bank[3] = new Account1("Marcus O'Hare", 71234, 500.0);
bank[4] = new Account1("Margaret Jones", 89761, 475.0);

System.out.println("Unsorted values");
output(bank);
mergeSort(bank);
System.out.println("Sorted values");
output(bank);
System.out.println("There are "+comparisons+" comparisons.");
}
 
public static void mergeSort(Comparable[] L)
{ 
     Comparable[] leftList, rightList;
 
     if(L.length > 1)
                      {
   int left = L.length/2;
   int right = L.length-left;
  leftList = new Comparable[left];
   rightList = new Comparable[right];
 

   for(int i = 0; i< left; i++)  leftList[i] = L[i];
   
   for(int i = 0; i< right; i++) rightList[i] = L[i+left];
 
   mergeSort(leftList);
   mergeSort(rightList);
 

int indexLeft = 0;
int indexRight = 0;
int indexOutput = 0;
while (indexLeft < left && indexRight < right)
{
if(leftList[indexLeft] .compareTo (rightList[indexRight])<0)
{
L[indexOutput] = leftList[indexLeft];
indexLeft++;
}else{
L[indexOutput] = rightList[indexRight];
indexRight++;
}
indexOutput++;
comparisons++;
}

while(indexLeft < left)
{
L[indexOutput] = leftList[indexLeft];
indexLeft++;
indexOutput++;
}
 
while(indexRight < right)
{
L[indexOutput] = rightList[indexRight];
indexRight++;
indexOutput++;
}
     }
 

}
 

public static void output(Account1[] data)
{
for(int i=0; i<data.length; i++)
System.out.println(data[i] + " ");

System.out.println();
} 

}    

I now have the following which i need to do - Create an array of Comparable Account objects in account number order (or use the output from the above code i have already completed) then implement a recursive Binary search for an item.

I'm not sure where to get started on this question. Any help would be appreciated. Thanks.

[Joe Grimp]

I have tried to get this started and have the following done so far but don't know if i am going in the right direction. If anyone could help that would be great.

 public class CW_Q2 {
 

import java.util.Scanner;

public class recBinarySearch
{
public static void main(String[] args) 
{

static int comparisons;
 
public static void main(String[] args)
{
Account[] bank = new Account[5];
double totalBal, smallestBal, largestBal;

bank[0] = new Account("Ted Murphy", 72354, 102.56);   
bank[1] = new Account("John Smith", 69713, 40.00);
bank[2] = new Account("Ted Murphy", 72354, 102.56);
bank[3] = new Account("Marcus O'Hare", 71234, 500.0);
bank[4] = new Account("Margaret Jones", 89761, 475.0);

System.out.println("Unsorted values");
output(bank);
mergeSort(bank);
System.out.println("Sorted values");
output(bank);
System.out.println("There are "+comparisons+" comparisons.");
}

Scanner kbScan = new Scanner (System.in);
System.out.println("Array of Values");
for (int i=0; i< grades.length; i++)
System.out.print(grades[i]+ " ");
System.out.println();
System.out.println("Item to be located?");
item = kbScan.nextInt();
result = containsBinary(grades, item, 0, grades.length-1);
if (result) System.out.println("Found ok");
else System.out.println("Not found");
}
public static boolean containsBinary(int myVals[], int target, int left, int right)
{int mid;
if (right < left) return false;
   else {mid = (left + right)/2;
   if (myVals[mid] == target) return true; 
   else if(target < myVals[mid]) return containsBinary(myVals, target, left, mid-1);
else return containsBinary(myVals, target, mid+1, right);
}
                   
   }
} 
 


public static void output(int[] data)
{
for(int i=0; i<data.length; i++)
System.out.print(data[i] + " ");

System.out.println();
} 
}