Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

MergeSort  RSS feed

 
Joe Grimp
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 -



I'm not sure of where to begin with this problem, and any help would be appreciated. Thanks.
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16028
87
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have decided to make the list of comparible objects Account objects -



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?? -



Thanks.
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16028
87
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

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:

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
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, i have completed this piece of code and it compiles and runs -




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
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!