• Post Reply Bookmark Topic Watch Topic
  • New Topic

Merge sort failure  RSS feed

 
Rahul Sudip Bose
Ranch Hand
Posts: 637
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am trying to develop a merge sort program on my own. I need it for another program. Everything works well, except last step. Please help me to solve this issue.
If the implementation of the idea is faulty, please let me know.

Basic overview of my code :

Note that duplicate data in the array is allowed.

CLASSES :

1. MergeSort -
It will take a float array, make a copy of that array and then perform merge sort on it using an inner class called "Bin". This class has main method.

2. Bin -
It has a float[] data, 3 references of type Bin. 1st ref is lhs , ie the left half of float[] data. 2nd is rhs. 3rd is parent which refers to the object of which it is a fragment.
It has a method split, which splits the given array into half. This method also makes a call to ITS merge method to do the merging.
Show method is to see the contents of float[] data of a Bin.

The code :


 
Rahul Sudip Bose
Ranch Hand
Posts: 637
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The output of this code :

The last line is wrong. Everything before that looks ok.

 
Paul Clapham
Sheriff
Posts: 22828
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You have output which looks like this:

Here I see two groups of numbers separated by a comma. In all instances except the last, there is no overlap between the two groups of numbers. To put it another way, every number in one group is larger than every number in the other group.

So my question is, is "every number in one group is larger than every number in the other group" supposed to be a result of your algorithm at every step? It appears that you are making that assumption when you combine the two groups. If that's the case, then there is something wrong with the part of the algorithm which produces the groups in the first place, and looking at the very end is the wrong approach. It's just that the problem doesn't show up until then.

However if that isn't an assumption you are making, then your method of combining the groups should merge them properly instead of simply assuming they can be concatenated.
 
Rahul Sudip Bose
Ranch Hand
Posts: 637
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wonder why it works well till the last step. Any place that gives clear code with detailed explanations ??? (Giving up because my approaches are producing junk.)

PS :
I though that algorithms are supposed to be fun, but its depressing, especially due to esoteric books like cormen.
 
Paul Clapham
Sheriff
Posts: 22828
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rahul Sudip Bose wrote:I wonder why it works well till the last step.

Just luck. Try it with a larger and more unordered array as your input.
Any place that gives clear code with detailed explanations ??? (Giving up because my approaches are producing junk.)

I'm sure that a Google search would lead to all kinds of pages about sorting.
I though that algorithms are supposed to be fun, but its depressing, especially due to esoteric books like cormen.

Different people have different ideas about what is fun. I'm sure if you got up and went out into the street and asked the first 100 people you met whether designing a sorting algorithm would be fun, you would get at least 99 "No" answers.

(Which is also the reason I haven't spent any time looking at your code. I'm perfectly willing to help you out by asking questions to push you in the right direction, though.)
 
Rahul Sudip Bose
Ranch Hand
Posts: 637
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Back to the drawing board then.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!