CODEWITHSUNDEEP
javalinked-listpriority-queueinsertion-sort
user3573301
user3573301

Reputation: 61

Priority queue Insertion sort

I'm supposed to implement an insertion sort method using linked lists in a priority queue. My problem is when it comes to sorting the last few elements it compares them but puts them in the wrong order. Here is my code.

PQInsertionSort class

 class PQInsertionSort
{
 Entry head;
int size;
public PQInsertionSort()
{
 head = null;
  size = 0;
}

public void insert(Entry elem) 
{

if (size == 0)
{
    System.out.println("1");

 head = elem;
}

else if(head.getKey() > elem.getKey())
{ 
    System.out.println("2");

    elem.setNext(head);
    head = elem;
}
else
{
     Entry curr;
     Entry prev;
      curr = head;
      prev = head;

    System.out.println("3");

    while(curr.getNext() != null && curr.getKey() < elem.getKey())
    {
        prev = curr;
        curr=curr.getNext();
        System.out.println("curr is "+ curr.getKey() + " elem is " +elem.getKey());

    } 

if(curr.getNext() != null)
{
     System.out.println("6");
    elem.setNext(prev.getNext());
    prev.setNext(elem);
    }
else
    {
    System.out.println("5");
    curr.setNext(elem);
    }

    }
  size++;
}

public Entry removeMin()
{
 Entry tmp = null;
 if (size == 0)
 {
   System.out.println("Queue is empty.");
 }
 else
 {
    tmp = head;
    head = head.getNext();
    size--;
 }
 if (size == 0)
 {
  head = null; 

  } 
   return tmp;
  }
public String min()
{

    return head.getName();

}

public int size()
{
  return size(); 
}

public boolean isEmpty()
{
return (head == null);

}

public void print()
{
 Entry p = head;
 while(p != null)
 {
     System.out.println(p.getKey() + p.getName());

     p = p.getNext();
 }

}

}

Entry Class

class Entry
{
  private int key;
  private String name;
  private Entry next;

  public Entry(int k, String n, Entry e)
  {
    key = k;
    name = n;

    next = e;

  }

  public void setNext(Entry e)
  {
    next = e;
  }

  public Entry getNext()
  {
    return next;
  }

  public int getKey()
  {
    return key;
  }

  public void setKey(int k)
  {
    key = k;
  }

  public String getName()
  {
    return name;
  }

  public void setName(String n)
  {
    name = n;  
  }
}

Tester Class

public class Test {

    public static void main(String[] args)
    {
        PQInsertionSort qs = new PQInsertionSort();

        qs.insert(new Entry(4, "Sam", null));
        qs.insert(new Entry(3, "Tim", null));
        qs.insert(new Entry(7, "Amanda", null));
        qs.insert(new Entry(1, "Chris", null));
        qs.insert(new Entry(2, "Jimbo", null));
        qs.insert(new Entry(5, "Melinda", null));
        qs.insert(new Entry(6, "Alice", null));

        qs.print();
    }

}

The output is this

1
2
3
prev is 4 elem is 7
5
2
3
prev is 3 elem is 2
6
3
prev is 2 elem is 5
prev is 3 elem is 5
prev is 4 elem is 5
prev is 7 elem is 5
5
3
prev is 2 elem is 6
prev is 3 elem is 6
prev is 4 elem is 6
prev is 7 elem is 6
6
1Chris
2Jimbo
3Tim
4Sam
6Alice
7Amanda
5Melinda

See how 5 is output as the lass elem. Any ideas?

Upvotes: 0

Views: 1060

Answers (1)

user3573301
user3573301

Reputation: 61

I seemed to figure it out. After the while loop I had to add another condition because it was passing straight to the else. so it should be like this.

if(curr.getNext() != null)
{
     System.out.println("6");
    elem.setNext(prev.getNext());
    prev.setNext(elem);

}
else if(curr.getKey() > elem.getKey())
{
    elem.setNext(prev.getNext());
    prev.setNext(elem);
}
else
    {
    System.out.println("5");

    curr.setNext(elem);
    }

}

Upvotes: 1

Related Questions