Bubble Sort Manually a Linked List in Java -
this first question here. trying manually sort linked list of integers in java , can not figure out wrong code. suggestions? don't error, still have output unordered. tried few different ways, nothing worked. appreciate if can me that.
public class node { int data; node nextnode; public node(int data) { this.data = data; this.nextnode = null; } public int getdata() { return this.data; } } // node class public class datalinkedlist implements datainterface { private node head; private int size; public datalinkedlist(){ this.head = null; this.size = 0; } public void add(int data) { node node = new node(data); if (head == null) { head = node; } else { node currentnode = head; while(currentnode.nextnode != null) { currentnode = currentnode.nextnode; } currentnode.nextnode = node; } size++; } public void sort() { if (size > 1) { (int = 0; < size; i++ ) { node currentnode = head; node next = head.nextnode; (int j = 0; j < size - 1; j++) { if (currentnode.data > next.data) { node temp = currentnode; currentnode = next; next = temp; } currentnode = next; next = next.nextnode; } } } } public int listsize() { return size; } public void printdata() { node currentnode = head; while(currentnode != null) { int data = currentnode.getdata(); system.out.println(data); currentnode = currentnode.nextnode; } } public boolean isempty() { return size == 0; } } // datainterface class public class dataapp { public static void main (string[]args) { datalinkedlist dll = new datalinkedlist(); dll.add(8); dll.add(7); dll.add(6); dll.add(4); dll.add(3); dll.add(1); dll.sort(); dll.printdata(); system.out.println(dll.listsize()); } } // dataapp class
the problem, expected, comes in method sort():
public void sort() { if (size > 1) { (int = 0; < size; i++ ) { node currentnode = head; node next = head.nextnode; (int j = 0; j < size - 1; j++) { if (currentnode.data > next.data) { node temp = currentnode; currentnode = next; next = temp; } currentnode = next; next = next.nextnode; } } } } a minor problem execute bubble sort n*n times. better check whether there change between pair in list. if was, there need run again on list; if not, there isn't. think of marginal case in list of 100 elements sorted when sort() called. means nodes in list run on 10000 times, when there nothing do!
the main problem, though, exchanging pointers nodes in list.
if (currentnode.data > next.data) { node temp = currentnode; currentnode = next; next = temp; } if translate currentnode v[i] , next v[i - 1], if sorting array, do. however, changing pointers use run on list, without effect in list itself. best solution (well, provided going use bubblesort, worst solution) exchange data inside nodes.
if (currentnode.data > next.data) { int temp = currentnode.data; currentnode.data = next.data; next.data = temp; } however, matter of illustration of concept, i'm going propose changing links among nodes. these pointers ones mark sorting in list. i'm talking nextnode attribute in node class.
enough chat, here is:
public void sort() { if (size > 1) { boolean waschanged; { node current = head; node previous = null; node next = head.nextnode; waschanged = false; while ( next != null ) { if (current.data > next.data) { /* // literal translation // of bubble sort in array node temp = currentnode; currentnode = next; next = temp;*/ waschanged = true; if ( previous != null ) { node sig = next.nextnode; previous.nextnode = next; next.nextnode = current; current.nextnode = sig; } else { node sig = next.nextnode; head = next; next.nextnode = current; current.nextnode = sig; } previous = next; next = current.nextnode; } else { previous = current; current = next; next = next.nextnode; } } } while( waschanged ); } } the explanation "double" code managing node exchange that, since have change links among nodes, , single linked list, have keep track of previous node (you don't have header node, either), first time head.
if ( previous != null ) { node sig = next.nextnode; previous.nextnode = next; next.nextnode = current; current.nextnode = sig; } else { node sig = next.nextnode; head = next; next.nextnode = current; current.nextnode = sig; } you can find code in ideone, here: http://ideone.com/hw5zw7
hope helps.
Comments
Post a Comment