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).


Comments

Post a Comment

Popular posts from this blog

java - Jmockit String final length method mocking Issue -

-
using jmockit 1.2 jar, trying mock string's length method getting unexpected invocation exception: failed: test java.lang.illegalstateexception: missing invocation mocked type @ point; please make sure such invocations appear after declaration of suitable mock field or parameter @ stringdemo.testa$1.<init>(testa.java:17) @ stringdemo.testa.test(testa.java:13) i using testng: @test public void test() throws exception { new expectations() { @mocked("length") string astring; { astring.length(); result = 2; } }; system.out.println(a.showa("test")); } } actual class a: public class { public static int showa(string str){ int a= str.length(); return a; } } this wrong way of recording expected results. shouldn't mock , record string's length() method, record showa() instead. here solution @suppresswarnings("unused...
Read more

What is the difference between data design and data model(ERD) -

-
i have google question , find answer in day. know, data design many many table have list column,and mark pk , fk. why er-diagram have find this? data design process of designing database. main output of data design detailed logical data model of database. some people data design includes of needed logical , physical design choices , physical storage parameters needed generate design in data definition language. technically, database analysis, database analysts (dbas) trained do. while person can both data design , database analysis, these 2 different tasks. data design models data. database analysis takes model , applies 1 or more database engines (relational, hierarchical, nosql). a logical data model 1 of main outputs of data design. data model represented entity relationship diagram, or er diagram.
Read more

ios - Can NSManagedObject conform to NSCoding -

-
i need transfer single object across device. right converting nsmanagedobject dictionary , archiving , sending nsdata. upon receiving unarchiving it. transfer nsmanagedobject archiving , unarchiving instead of creating intermediate data object. @interface test : nsmanagedobject<nscoding> @property (nonatomic, retain) nsstring * title; @end @implementation test @dynamic title; - (id)initwithcoder:(nscoder *)coder { self = [super init]; if (self) { self.title = [coder decodeobjectforkey:@"title"]; //<crash } return self; } - (void)encodewithcoder:(nscoder *)coder { [coder encodeobject:self.title forkey:@"title"]; } @end nsdata *archivedobjects = [nskeyedarchiver archiveddatawithrootobject:testobj]; nsdata *objectsdata = archivedobjects; if ([objectsdata length] > 0) { nsarray *objects = [nskeyedunarchiver unarchiveobjectwithdata:objectsdata]; } the problem above code is. crashes @ self.title in initwithcoder sa...
Read more