• Post Reply Bookmark Topic Watch Topic
  • New Topic

merge Sort java and linked list  RSS feed

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've playing around with linked lists and methods for sorting. So far I've tested the iterative sort, insertion sort, quick sort and they all worked perfectly. Now, I am trying to implement merge sort that would take a linked list of jobs and sort them according to their priority. I found a few solutions on the web, of which I am trying to implemented this one: LeetCode.

My system is a simple one, I do have a linked list of print jobs, each of which has the priority. The following code should sort my print queue and return the link node of the first sorted element. Here's the code.

//defining a job that has priority



// defining a linked list of elements


//recursive merge sort - this consists of two methods, the first that recursively breaks the linked list into half and half and so on, and the second, which compares the priorities of the individual jobs in nodes.


The problem I've been trying to solve is that I am getting the stack overflow at line

ListNode<T> h1 = mergeSort(left);

meaning that I am getting into a loop somewhere down through the process of breaking the linked list into half, half or halfs and so on. I would be grateful if you can point me to the right direction, because I've double checked everything, and right now I am not sure to see where the error might be. Thanks for any input.

This post loosely follows the previous post on BMS BSM - linked lists
 
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That method looks too long. It also looks more complicated than other merge sorts I have seen. Even without reading it, which is very difficult because you haven't indented the code correctly. We hva some suggestions about indentation here.

Read this, which suggests you shouldn't sort linked lists, and tells you what to do instead. you should also not rely on the elements in the list having priorities. That produces a brittle solution which works only for your Job class. The standard implementation requiring a Comparable or Comparator has universal applicability.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you really want to follow the leet code solution, be sure to copy it exactly.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is something not quite correct about setting two values to point at nextNode (lines 19-21). Are you sure that is what you want?
What is queLength which you are halving? How is that set?
 
Michal Kovac
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:There is something not quite correct about setting two values to point at nextNode (lines 19-21). Are you sure that is what you want?
What is queLength which you are halving? How is that set?


First, let me thank you for your time and suggested readings. Really appreciated.

Second, I know, but in this case I am not allowed to use any pre-defined collection classes.

Third, private static int queLength; is the number of linked nodes in a queue. Every time a node is added it is increased (and decreased when a node is dequeued). So if I want to break a linked list in the middle, I would iterate through the list to the middle, set the next to null and switch to a new right linked list. I've been running this part without recursion, and it seemed to work.

EDIT: yes, I was able to implement a solution which dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. Now I am a bit curious about the other possibilities. Again, thanks for your time and help.
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Michal Kovac wrote:EDIT: yes, I was able to implement a solution which dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. Now I am a bit curious about the other possibilities.

The main problem is that a sort on a linked list is likely to be very involved, whereas one on an array is very straightforward. That's not to say it can't be done, but I suspect that you're going to want to break down the problem into a series of "swaps" which you test very thoroughly. It's not actually that much different to an array sort, but all the re-jigging of pointers makes things:
  • A lot more complicated.
  • Easier to get wrong.
  • Tougher to figure out why it went wrong if it does.


  • But don't let that stop you if you're determined.

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