Click here to Skip to main content
15,888,803 members
Home / Discussions / Java
   

Java

 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
TheLaughingManAnDerTU25-Apr-11 10:29
TheLaughingManAnDerTU25-Apr-11 10:29 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
Manfr3d25-Apr-11 12:20
Manfr3d25-Apr-11 12:20 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
JavaStudent_LA25-Apr-11 16:11
JavaStudent_LA25-Apr-11 16:11 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
Manfr3d25-Apr-11 22:46
Manfr3d25-Apr-11 22:46 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
TheLaughingManAnDerTU26-Apr-11 6:04
TheLaughingManAnDerTU26-Apr-11 6:04 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
Manfr3d27-Apr-11 0:05
Manfr3d27-Apr-11 0:05 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
JavaStudent_LA29-Apr-11 15:17
JavaStudent_LA29-Apr-11 15:17 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
Manfr3d30-Apr-11 3:41
Manfr3d30-Apr-11 3:41 
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.
GeneralRe: In-place Merge-Sort with doubly linked list Pin
JavaStudent_LA3-May-11 16:26
JavaStudent_LA3-May-11 16:26 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
Manfr3d3-May-11 21:58
Manfr3d3-May-11 21:58 
GeneralMessage Removed Pin
4-May-11 4:44
JavaStudent_LA4-May-11 4:44 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
Manfr3d4-May-11 7:32
Manfr3d4-May-11 7:32 
GeneralRe: In-place Merge-Sort with doubly linked list Pin
JavaStudent_LA8-May-11 11:41
JavaStudent_LA8-May-11 11:41 
Questionmysql to oracle conversion tool Pin
ankit.mathurs21-Apr-11 16:39
ankit.mathurs21-Apr-11 16:39 
AnswerRe: mysql to oracle conversion tool Pin
TorstenH.21-Apr-11 22:56
TorstenH.21-Apr-11 22:56 
Questionform validations in java Pin
ships_agr20-Apr-11 23:47
ships_agr20-Apr-11 23:47 
AnswerRe: form validations in java Pin
TorstenH.21-Apr-11 1:36
TorstenH.21-Apr-11 1:36 
GeneralRe: form validations in java Pin
ships_agr21-Apr-11 20:19
ships_agr21-Apr-11 20:19 
GeneralRe: form validations in java Pin
TorstenH.21-Apr-11 22:36
TorstenH.21-Apr-11 22:36 
GeneralRe: form validations in java Pin
ships_agr25-Apr-11 9:15
ships_agr25-Apr-11 9:15 
QuestionProblem with my code Pin
mofuobi20-Apr-11 23:45
mofuobi20-Apr-11 23:45 
AnswerRe: Problem with my code Pin
TorstenH.21-Apr-11 1:30
TorstenH.21-Apr-11 1:30 
QuestionIWAB0380E Errors were encountered while validating XML schemas. XSD: Pin
R V Reddy20-Apr-11 20:07
R V Reddy20-Apr-11 20:07 
AnswerRe: IWAB0380E Errors were encountered while validating XML schemas. XSD: Pin
Peter_in_278020-Apr-11 20:45
professionalPeter_in_278020-Apr-11 20:45 
AnswerRe: IWAB0380E Errors were encountered while validating XML schemas. XSD: Pin
TorstenH.20-Apr-11 22:08
TorstenH.20-Apr-11 22:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.