|
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.
|
|
|
|
|
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.
|
|
|
|
|
I'm gonna write you down a few lines the next days, but at the moment I'm quite busy.
|
|
|
|
|
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.
|
|
|
|
|
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 ) {
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 ) {
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
this function also calls the 3-argument version of mergesort
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 .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.
|
|
|
|
|
|
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
|
|
|
|
|
i am working on mysql to oracle conversion tool but i m facing problem to convert mediumblob data type tooracle medium blob data type any one help me for this problem with runnable code
|
|
|
|
|
|
I am developing an intranet system using net beans.I did all the designing using dreamweaver and for the code part i will use servlet.So i want to know about the options for applying validations(required field,email validation,format) in my project other than java script.
|
|
|
|
|
hmm, you could validate at different occasions. First is the entry field - last chance is when the data is received and used (e.g. an object is created).
Simple things like the required fields can easily be validated by the form itself.
The format of certain values should be validated by the receiver of the data.
regards
Torsten
I never finish anyth...
|
|
|
|
|
sir thanks for your unfinished reply.
that all i understood....but can you please give an example of validating a textfield on client side.....i don't want to perform any server side validation.
|
|
|
|
|
|
thanks a lot.....this one is of gr8 help to me......act i'm new to dreamweaver nd don know it deeply......ur 1st reply was unfinished as ur tag line says u nvr finish nething ......neways.....i nvr thot that i can do this using dreamweaver also.
|
|
|
|
|
public static Intent getIntentForHome(Activity paramActivity, int paramInt)<br />
{<br />
if ((paramActivity == null) || (paramInt == -1));<br />
Intent localIntent1;<br />
for (Object localObject = null; ; localObject = localIntent1)<br />
{<br />
<pre> return localObject;</pre><br />
localIntent1 = new Intent(paramActivity, HomesMapActivity.class);<br />
Intent localIntent2 = localIntent1.setAction("android.intent.action.VIEW");<br />
Intent localIntent3 = localIntent1.putExtra("android.intent.extra.TEXT", paramInt);<br />
}<br />
}
if finish writing this an i got a error saying this at the selected code block
Multiple markers at this line
- Type mismatch: cannot convert from Object
to Intent
- Type mismatch: cannot convert from Object
to Intent
|
|
|
|
|
public static Intent getIntentForHome(Activity paramActivity, int paramInt) {
Intent localIntent1;
for (Object localObject = null; ; localObject = localIntent1) {
return localObject;
}
}
That's a bit of a mess.
Your function states to give back a "Intent":
public static Intent getIntentForHome()
But the return value is a "Object":
for (Object localObject = null; ; localObject = localIntent1) {
return localObject;
}
You need to cast it at least to an "Intent" or - even better - declare it as a "intent" right away.
regards
Torsten
I never finish anyth...
|
|
|
|
|
IWAB0380E Errors were encountered while validating XML schemas.
XSD: The location 'CalculatorService_schema1.xsd' has not been resolved
IWAB0381I http://localhost:8080/WebServiceProject/CalculatorService.wsdl was successfully opened.
Does anyone know what this means? Plz Help me.....
|
|
|
|