Shahab_HK Shahab_HK - 6 days ago 5
Java Question

Linked list merge sort using java

I want to implement merge sort just with linked list without any array, using java. But i got stuck in a logical error; my code eliminates some inputs and sorts the remains. I have applied three class:

Divide
,
Merg
,
MergSort
as below:

public class Divide {

List firstList = new List();
List secondList = new List();

public int GetLength(List list) {
int Length = 0;
Link temp = new Link();
temp.next = list.head.next;
while (temp.next != null) {
temp.next = temp.next.next;
Length++;
}

return Length;
}

public List rightSide(List list) {
int Length = GetLength(list);
Link temp = new Link();
temp.next = list.head.next;

for (int i = 1; i <= Math.floor(Length / 2); i++) {
firstList.Insert(temp.next.data);
temp.next = temp.next.next;
}
return firstList;
}

public List leftSide(List list) {
int Length = GetLength(list);
Link temp = new Link();
temp.prev = list.head.prev;

for (int i = 1; i <= Math.ceil(Length / 2); i++) {
secondList.Insert( temp.prev.data);
temp.prev = temp.prev.prev;
}
return secondList;
}
}


merge:

public class Merg {

public List MergedList = new List();
private List Temp = new List();

public List Merg (List one, List two)
{
Link onelink = new Link();
Link twolink = new Link();

onelink.next = one.head.next;
twolink.next = two.head.next;

while (onelink.next!= null || twolink.next!= null)
{

if(onelink.next!= null && twolink.next != null)
{
if(onelink.next.data < twolink.next.data)
{
Temp.Insert(onelink.next.data);
onelink.next = onelink.next.next;
}
else
{
Temp.Insert(twolink.next.data);
twolink.next = twolink.next.next;
}

}

if (onelink.next != null && twolink.next == null)
{
Temp.Insert(onelink.next.data);
onelink.next = onelink.next.next;
}
if (twolink.next != null && onelink.next == null)
{
Temp.Insert(twolink.next.data);
twolink.next = twolink.next.next;
}

}

if (Temp.head.next.data > Temp.head.prev.data)
{
while (Temp.head.next != null)
{
MergedList.Insert(Temp.head.next.data);
Temp.head.next = Temp.head.next.next;
}
}

else
{
MergedList.head.next = Temp.head.next;
}


return MergedList;
}

}


MergSort:

public class MergSort {

public List mergSort (List list)
{
Divide divide = new Divide();
Merg merg = new Merg();

if (divide.GetLength(list) > 1) {
return merg.Merg(mergSort(divide.leftSide(list)), mergSort(divide.rightSide(list)));
}
else
{
return list;
}
}
}


Although i have wrote the
link
and
list
classes too, but i think there is no trouble in there. (However if it was necessary i will mention them)
Now, when i import some inputs such that : {100,3,1,7,6} the Output is: 3,6,7,100. (1 has been eliminated!) or another example: {100,3,1} the output is: 1,100 (where is 3??)

I wonder if someone can help me...

Link:

public class Link {
public double data;
public Link prev;
public Link next;
}


list:

public class List {
public Link head = new Link();

public void setHead(Link head) {
this.head = head;
head.prev = null;
head.next = null;
}

public void Insert(double x)
{
Link link = new Link();
link.data = x;
if (head.next == null)
{
head.next = link;
head.prev = link;
}
else
{
head.next.prev = link;
link.next = head.next;
head.next = link;
}
}

public Link delete()
{
Link temp = new Link();
temp = head;
head = head.next;
return temp;
}

public Link search(double x)
{
Link link = new Link();
link.next = head;
while (link.next.data != x)
{
link.next = link.next.prev;
}

return link.next;
}
}

Answer

I have debugged a lot but I can't make sense of your Divide class. You don't need it at all.

public class MergSort {

    public List mergSort(List list) {
        Divide divide = new Divide();
        Merg merg = new Merg();
        int n = list.getLength();
        if (n > 1) {
//            return merg.Merg(mergSort(divide.leftSide(list)), mergSort(divide.rightSide(list)));
            Link cursor = list.head.next;
            List left = new List();
            List right = new List();
            // for (i = 0; ....... i will be 0 if head is not dummy
            for (int i = 1; cursor != null; i++) {
                if (i <= n/2)
                    left.Insert(cursor.data);
                else
                    right.Insert(cursor.data);
                cursor = cursor.next;
            }
            left = mergSort(left);
            right = mergSort(right);

            return merg.Merg(left, right);

        } else {
            return list;
        }
    }
}

Create a getLength() method in your List class. It should be in List class because you want the length of your list.

public int getLength() {
    int Length = 0;
    Link temp = head.next;
    while (temp != null) {
        temp = temp.next;
        Length++;
    }

    return Length;
}

Also, rename your Link class to Node. Because a Link means a link between to objects or an edge between nodes. What you really want is a Node. It's confusing.

In your List class, you have defined head like this:

public Link head = new Link();

I don't see why you would need a dummy headed linked list.

A linked list with a dummy head is basically a head with no values and hence dummy.

enter image description here

Because of your dummy head, you are starting your for loops in Divide class from i = 1. Why complicate things? If you really need a dummy head, then keep it or define it like this:

public Link head;
// don't instantiate the head. It's just a reference

Also, you seem to create a half-circular linked list. What I mean by that is that the head.prev points to the last link/node in the list. If you truly want a circular linked list then point your tail.next to head.

Here is what a circular linked list looks like:

enter image description here

Or if you don't want a circular list, then don't point your head.prev to the last object.

In your Insert() method in List.java:

if (head.next == null)
{
    head.next = link;
    // remove head.prev = link;
}