In-place Merge-Sort with doubly linked list
-
Hello guys, I have to write an in-place version of Merge-Sort which works on doubly linked lists for university. This wouldn't be the problem, but there are a few conditions to meet. - the algo must work in-place (additional memory usage in O(log n)) - I cannot create new list elements or entire lists, just copies (ListElement left = new List Element() isn't possible but ListElement left = first is possible) - the algo should be recursive, but this is not necessary - each call of the algo must return a head pointer to the first element of the sub-list - the merge part must also return a head pointer
public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) {
if (numOfElements > 1) { DoublyLinkedList firstLeft = in; DoublyLinkedList firstRight = in; for ( int i = 0; i < numOfElements / 2; i++ ) { firstRight.first = firstRight.first.next; } DoublyLinkedList left = mergesort ( firstLeft, (int)Math.floor(numOfElements / 2 ) ); DoublyLinkedList right = mergesort ( firstRight, (int)Math.ceil(numOfElements / 2 ) ); return merge ( left, right ); } else { return in; }}
My problem is that I'm somehow stuck right at the beginning. The algo itself shouldn't be the problem, but the additional conditions make the whole thing quite difficult for me. Of course I've already searched for useful algos or something, but I didn't find anything. Thanks in advance for your help and best wishes, Manfred
-
Hello guys, I have to write an in-place version of Merge-Sort which works on doubly linked lists for university. This wouldn't be the problem, but there are a few conditions to meet. - the algo must work in-place (additional memory usage in O(log n)) - I cannot create new list elements or entire lists, just copies (ListElement left = new List Element() isn't possible but ListElement left = first is possible) - the algo should be recursive, but this is not necessary - each call of the algo must return a head pointer to the first element of the sub-list - the merge part must also return a head pointer
public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) {
if (numOfElements > 1) { DoublyLinkedList firstLeft = in; DoublyLinkedList firstRight = in; for ( int i = 0; i < numOfElements / 2; i++ ) { firstRight.first = firstRight.first.next; } DoublyLinkedList left = mergesort ( firstLeft, (int)Math.floor(numOfElements / 2 ) ); DoublyLinkedList right = mergesort ( firstRight, (int)Math.ceil(numOfElements / 2 ) ); return merge ( left, right ); } else { return in; }}
My problem is that I'm somehow stuck right at the beginning. The algo itself shouldn't be the problem, but the additional conditions make the whole thing quite difficult for me. Of course I've already searched for useful algos or something, but I didn't find anything. Thanks in advance for your help and best wishes, Manfred
Coincidentally, I have to do the exact same thing. I believe recursion might be the most efficient, good thing you've already started it that way. The code you have looks simple/efficient. HOWEVER, it looks like you followed the algorithm given to you in the "Skriptum". ;) Through some searching without using the keyword "pseudocode", I came across this very descriptive page which I have yet to take the time to fully comprehend (http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html)
-
Coincidentally, I have to do the exact same thing. I believe recursion might be the most efficient, good thing you've already started it that way. The code you have looks simple/efficient. HOWEVER, it looks like you followed the algorithm given to you in the "Skriptum". ;) Through some searching without using the keyword "pseudocode", I came across this very descriptive page which I have yet to take the time to fully comprehend (http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html)
-
In the meantime I wrote a fully working recursive implementation. However, I'm now working on an iterative version, because I'm not that fan of recursion for performance reasons.
I hope your iterative version has a less than linear auxiliary space requirement.
-
I hope your iterative version has a less than linear auxiliary space requirement.
It has, but if I execute the program, I get an MAC error message "Segmentation fault". I got this one time with the recursive version, but the next run finished without any errors? Does anyone know what can cause this error, a simple Java program shouldn't do this.
-
It has, but if I execute the program, I get an MAC error message "Segmentation fault". I got this one time with the recursive version, but the next run finished without any errors? Does anyone know what can cause this error, a simple Java program shouldn't do this.
This is really an interesting Assingment. Ive worked with MergeSort but I didnt have the Idea before that it could be effectivly implemented with DoublyLinked Lists. I would give this a try. I hope you guys will help me also :) P.S. I want to implement this in C++ with Stack. I think Stack here can do a lot of work :~ do you have any pseudocode, so I start it easily.
-
This is really an interesting Assingment. Ive worked with MergeSort but I didnt have the Idea before that it could be effectivly implemented with DoublyLinked Lists. I would give this a try. I hope you guys will help me also :) P.S. I want to implement this in C++ with Stack. I think Stack here can do a lot of work :~ do you have any pseudocode, so I start it easily.
-
Indeed, a doubly linked list can make this easy, but I can already imagine it working with a singly linked list. Any idea if having a cyclical list would be of any advantage over an acyclical one?
-
Indeed, a doubly linked list can make this easy, but I can already imagine it working with a singly linked list. Any idea if having a cyclical list would be of any advantage over an acyclical one?
In my opinion it's not an advantage for the algorithm. It can be an advantage when dealing with the data structure itself. However, if you split the list, you have to reconnect the first to the last element of the sub-list and vice versa. It's also not that easy to check whether you reached the last element, cause you need help pointers or something similar.
-
In my opinion it's not an advantage for the algorithm. It can be an advantage when dealing with the data structure itself. However, if you split the list, you have to reconnect the first to the last element of the sub-list and vice versa. It's also not that easy to check whether you reached the last element, cause you need help pointers or something similar.
aghhh, I can't get it finished :-( I've been spending on it my whole day. Hey Manfr3d maybe you can help me with your version-code?
-
aghhh, I can't get it finished :-( I've been spending on it my whole day. Hey Manfr3d maybe you can help me with your version-code?
OK, here is a pseudo code version of my implementation.
DLL mergesort ( DLL in, int n ) { // in is the list head, n the number of elements to sort
check for special cases and handle them separately: in == null, n == 0; n == 1; n == 2 => rearrange if necessary
m = floor ( n / 2 )
get first and last elements of left and right sub-lists: f.e. with a for-loop then the left first is the element pointed at by the list head, the right last is the previous of this,
last left and first right are at position m and m+1
wrap around left and right sub-lists
mergesort ( in, m, first left )
first left = in.first
mergesort ( in, n-m, first right )
first right = in.first
merge ( first left, first right )
return in
}
mergesort ( DLL in, LE first, int n ) { // in: head, first: first list element, n: number of elements
as the mergesort function above, except that the trivial case n == 1 must be handled, because this is the break condition for the recursion
if n == 1 => in.first = first // in.first means the first element of the list
this function also calls the 3-argument version of mergesort // the 2-argument version is just the entry point
all list elements must be addressed via the first one, not via the head, the head is just needed for the trivial case to connect the single LE to it
recursive calls and merge as above
return
}
merge (DLL in, LE first left, LE first right, int n ) {
first decide if the first element is of the left or the right sub-list, connect it to the head and move one step fwd in the sub-list
finished = f
counter = 1
while ( counter < n && !finished ) {
if next element is of left sub-list and it is not the first one => connect it to the sorted list, move fwd one step
else if next element is of right sub-list => same for right sub-list
else if the beginning of one sub-list is reached again => connect the other one to the sorted list, finished = t
move one step fwd in sorted list so that you are at the current end
counter++
}
return
}I know that this looks somehow quick and dirty, but if you have any questions feel free to ask.
-
OK, here is a pseudo code version of my implementation.
DLL mergesort ( DLL in, int n ) { // in is the list head, n the number of elements to sort
check for special cases and handle them separately: in == null, n == 0; n == 1; n == 2 => rearrange if necessary
m = floor ( n / 2 )
get first and last elements of left and right sub-lists: f.e. with a for-loop then the left first is the element pointed at by the list head, the right last is the previous of this,
last left and first right are at position m and m+1
wrap around left and right sub-lists
mergesort ( in, m, first left )
first left = in.first
mergesort ( in, n-m, first right )
first right = in.first
merge ( first left, first right )
return in
}
mergesort ( DLL in, LE first, int n ) { // in: head, first: first list element, n: number of elements
as the mergesort function above, except that the trivial case n == 1 must be handled, because this is the break condition for the recursion
if n == 1 => in.first = first // in.first means the first element of the list
this function also calls the 3-argument version of mergesort // the 2-argument version is just the entry point
all list elements must be addressed via the first one, not via the head, the head is just needed for the trivial case to connect the single LE to it
recursive calls and merge as above
return
}
merge (DLL in, LE first left, LE first right, int n ) {
first decide if the first element is of the left or the right sub-list, connect it to the head and move one step fwd in the sub-list
finished = f
counter = 1
while ( counter < n && !finished ) {
if next element is of left sub-list and it is not the first one => connect it to the sorted list, move fwd one step
else if next element is of right sub-list => same for right sub-list
else if the beginning of one sub-list is reached again => connect the other one to the sorted list, finished = t
move one step fwd in sorted list so that you are at the current end
counter++
}
return
}I know that this looks somehow quick and dirty, but if you have any questions feel free to ask.
I asked for little and you gave me a lot of help. I really have to thank you. Im gonna end this assigmend coz it has already spend a lot of my time. Ill give this Pseudocode a try and see what happens. I hope its functional. So I immediatly have a question. Im a little confuzed here: " mergesort ( DLL in, LE first, int n ) { // in: head, first: first list element, n: number of elements as the mergesort function above, except that the trivial case n == 1 must be handled, because this is the break condition for the recursion if n == 1 => in.first = first // in.first means the first element of the list this function also calls the 3-argument version of mergesort // the 2-argument version is just the entry point all list elements must be addressed via the first one, not via the head, the head is just needed for the trivial case to connect the single LE to it recursive calls and merge as above return } " This is very roughly written. I suerly need more explanation on this :confused: .Thnx again
-
I asked for little and you gave me a lot of help. I really have to thank you. Im gonna end this assigmend coz it has already spend a lot of my time. Ill give this Pseudocode a try and see what happens. I hope its functional. So I immediatly have a question. Im a little confuzed here: " mergesort ( DLL in, LE first, int n ) { // in: head, first: first list element, n: number of elements as the mergesort function above, except that the trivial case n == 1 must be handled, because this is the break condition for the recursion if n == 1 => in.first = first // in.first means the first element of the list this function also calls the 3-argument version of mergesort // the 2-argument version is just the entry point all list elements must be addressed via the first one, not via the head, the head is just needed for the trivial case to connect the single LE to it recursive calls and merge as above return } " This is very roughly written. I suerly need more explanation on this :confused: .Thnx again
This function is nearly the same as the above one. However, the 2-argument version (I will call it ms2 from now on, and the 3-argument version ms3) was just the, one could say, "standardized interface" that must be used. ms2 calls ms3 like it is the same function. You could also call ms3 just once within ms2, resulting in one more level on the call stack. The implementations of the functions are equal, except for the fact, that the head in ms3 is just used as a return value, which isn't returned at all, because it is accessible in the caller, even if modified. All copies, pointers and auxiliary LEs are assigned referring to the first element. This consumes less time, and is easier in my opinion, even though I wouldn't say that it's impossible without this additional parameter. And of course the trivial case must be caught in ms3 to end the recursion, which isn't necessary in ms2.
-
This function is nearly the same as the above one. However, the 2-argument version (I will call it ms2 from now on, and the 3-argument version ms3) was just the, one could say, "standardized interface" that must be used. ms2 calls ms3 like it is the same function. You could also call ms3 just once within ms2, resulting in one more level on the call stack. The implementations of the functions are equal, except for the fact, that the head in ms3 is just used as a return value, which isn't returned at all, because it is accessible in the caller, even if modified. All copies, pointers and auxiliary LEs are assigned referring to the first element. This consumes less time, and is easier in my opinion, even though I wouldn't say that it's impossible without this additional parameter. And of course the trivial case must be caught in ms3 to end the recursion, which isn't necessary in ms2.
I think I have a little bit of a Problem with my first Function!!! And I have to say, I hate recursion. OMG, it is goin' to kill me. I haven't worked with recursive functions before. Here is my code for my 1st func.
public DoublyLinkedList mergesort(DoublyLinkedList in, int n) { int middle=(int)Math.floor(n/2); ListElement firstLeft=in.first; ListElement lastLeft=firstLeft; for(int i=0; i -
I think I have a little bit of a Problem with my first Function!!! And I have to say, I hate recursion. OMG, it is goin' to kill me. I haven't worked with recursive functions before. Here is my code for my 1st func.
public DoublyLinkedList mergesort(DoublyLinkedList in, int n) { int middle=(int)Math.floor(n/2); ListElement firstLeft=in.first; ListElement lastLeft=firstLeft; for(int i=0; iWell, I'm not that friend of recursion, too, but my iterative solution killed the testing framework ^^ Your for-loop has to start at 1, else you reach the first element of the right sub-list. The 2nd for-loop is redundant.
lastRight = in.first.previous;will do the same much quicker and less error-prone. Except for the missing recursive calls, the merge part and testing for special cases, it doesn't look so bad. -
Well, I'm not that friend of recursion, too, but my iterative solution killed the testing framework ^^ Your for-loop has to start at 1, else you reach the first element of the right sub-list. The 2nd for-loop is redundant.
lastRight = in.first.previous;will do the same much quicker and less error-prone. Except for the missing recursive calls, the merge part and testing for special cases, it doesn't look so bad.hey Manfr3d , can you write me the linecodes for methode: merge ( first left, first right ) thnx