java - Quicksort Linked List Pivot Last Element -

i'm trying implement quicksort sorting cyclic linked list!

there doublylinkedlist contains listelements.

the listelement has element first, has reference predecessor , successor.

e.g. doublelinkyedlist in contains listelement first. first can referenced first.prev oder first.next.

the last element in linked list has reference first element e.g. last = first.prev;

my problem is, keep getting error, don't know 1 precisely, cause it's never ending loop , terminal not printing precise exception.

my code of class sorter.java implement sorting operation:

package ads1ss13.pa;   public class sorter {  public doublylinkedlist quicksort(doublylinkedlist in, int numofelements) {       system.out.println("starte sort() in quicksort()");      in = sort(in, in.first.getid(), in.first.prev.getid());      return in; }  public doublylinkedlist sort(doublylinkedlist in, int l, int r) {     system.out.println("sort()");      l = in.first.getid();     r = in.first.prev.getid();     listelement pivot = null;      system.out.println("l: "+l+"; r: "+r);      if(l < r)     {         pivot = in.first.prev;     }      system.out.println("pivot: "+pivot);      system.out.println("ausfuehren der partition mit l, r, pivot");      int p = partition(in, l, r, pivot);      system.out.println("ausgabe aus partition p: "+p);      system.out.println("ausführen der sort() mit l und p-1 für r");       sort(in, l, p-1);      system.out.println("ausführen der sort() mit p+1 für l, und r");     sort(in, p+1, r);      return in; }  public int partition(doublylinkedlist in, int l, int r, listelement pivot) {     system.out.println("partition()");      int = l;     int j = r;     listelement r_listelement = in.first.prev;     listelement i_element = in.first.next;     listelement j_element = pivot;      system.out.println("i: "+i+"; j: "+j+", pivot: "+j_element);      {          {             = + 1;             i_element = i_element.next;         } while (i_element.getkey() < pivot.getkey());          {             j = j - 1;             j_element = j_element.prev;          } while (j > || j_element.getkey() > pivot.getkey());          if(i_element.getkey() < j_element.getkey())         {             swap(in, i_element, j_element);         }      } while (i < j);      swap(in, i_element, r_listelement);      return i; }  public void swap(doublylinkedlist in, listelement links, listelement rechts) {     if(links.next.getid()==rechts.getid()){          listelement lprev = links.prev;         listelement rnext = rechts.next;         lprev.next=rechts;         rechts.prev=lprev;         links.next=rnext;         rnext.prev=links;         links.prev=rechts;         rechts.next=links;          }          else if(rechts.next.getid()==links.getid())         {             swap(in, rechts, links);         }         else         {             listelement lprev=links.prev;             listelement lnext = links.next;              links.next=rechts.next;             links.prev=rechts.prev;             rechts.next=lnext;             rechts.prev=lprev;              links.prev.next=links;             links.next.prev=links;             rechts.prev.next=rechts;             rechts.next.prev=rechts;         }           if(in.first.getid()==links.getid())         {             in.first = rechts;         }         else if(in.first.getid()==rechts.getid())         {             in.first = links;          } } } 

do have idea why code never switches second recursive call of sort() , error returned?

this hard analyze because can't throw code debugger. however, few things on right track:

issue 1.

you take int l , int r arguments, yet overwrite them:

l = in.first.getid(); r = in.first.prev.getid(); 

this not want do, restart on , on again. what's causing infinite loop.

issue 2.

if(l < r) {     pivot = in.first.prev; } 

if l >= r, pivot null, cause nullpointerexception

issue 3.

your partition logic wrong. don't need have nested loop. compare element pivot, can swap (you know side of pivot supposed on).