Doubly Linked List Bubble Sort

i am having a small problem.

Page 1 of 1

2 Replies - 5541 Views - Last Post: 16 December 2009 - 03:41 PM Rate Topic: -----

#1 Ricendithas  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 59
  • Joined: 12-July 08

Doubly Linked List Bubble Sort

Post icon  Posted 16 December 2009 - 03:03 AM

Hi! I have these codes.

	public void bubbleSortList() {
		boolean swap = false;
				
		for(SortNode ptr = tail; ptr != head; ptr = ptr.prev) {
			for(SortNode iPtr = head; iPtr.next != ptr; )
				if(iPtr.info.compareTo(iPtr.next.info) > 0) {
					iPtr = swap(iPtr, iPtr.next);
					swap = true;
				}
				else
					iPtr = iPtr.next;

			if(!swap)
				break;
		}		
	}
	
	public SortNode swap(SortNode a, SortNode B)/> {
		SortNode tempA, tempB = tempA = null;
	
		if(a == head) {
			head = b;
			tempB = b.next;
			
			a.prev = a.next = b.prev = b.next = null;
			
			b.next = a;
			
			a.next = tempB;
			a.prev = b;
			
			tempB.prev = a;
		}
		else if(b == tail){
			tail = a;
			tempA = a.prev;
			
			a.prev = a.next = b.prev = b.next = null;
			
			b.next = a;
			b.prev = tempA;
			
			a.prev = b;
			
			tempA.next = b;
			System.out.println("pass");
		}
		else if(a != head && b != tail) {
			tempA = a.prev;
			tempB = b.next;
			
			a.prev = a.next = null;
			b.prev = b.next = null;
			
			tempA.next = a.prev = b;
			tempB.prev = b.next = a;
			
			a.next = tempB;
			b.prev = tempA;			
		}
		else
			return b;
			
		return a;
	}



The problem is, whenever I try to sort a doubly linked list, everything is sorted except the last item.

Example:

003124
009780
023332
024948
027244
028015
029916
033073
052954
054753
063463
075512
076809
077326
078121
078428
084600
087830
093035
028996

028996 is not put in the proper place.

I have spent almost 3 hours figuring out why this happens. Any help would be appreciated. Thanks. :)

Is This A Good Question/Topic? 0
  • +

Replies To: Doubly Linked List Bubble Sort

#2 Paul-  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 61
  • View blog
  • Posts: 260
  • Joined: 11-December 09

Re: Doubly Linked List Bubble Sort

Posted 16 December 2009 - 08:35 AM

Your inner for loop seems to be one step short. Also, if the node pointed to by "ptr" gets swapped out, "ptr" needs to be updated. Try the following instead:

		for(SortNode ptr = tail; ptr != head; ptr = ptr.prev) {
			for(SortNode iPtr = head; iPtr != ptr; )
				if(iPtr.info.compareTo(iPtr.next.info) > 0) {
					iPtr = swap(iPtr, iPtr.next);
					// need to update ptr if the last element was swapped out:
					if (iPtr == ptr) {
						ptr = ptr.next;
					}
					swap = true;
				}
				else
					iPtr = iPtr.next;

			if(!swap)
				break;
		}		


Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10649
  • View blog
  • Posts: 39,548
  • Joined: 27-December 08

Re: Doubly Linked List Bubble Sort

Posted 16 December 2009 - 03:41 PM

Why go to all the trouble of swapping the Nodes? Just swap the elements at each Node. It is significantly more efficient than re-arranging the pointers for previous and next foreach Node.

@Paul: Bubble Sort actually starts at the head and head+1 elements iterating through the list, not the head and tail elements working towards the center.

Here is a basic algorithm I'd use:
0. Begin
1. temp <-- head
2. temp2 <-- head.next
3. boolean isSorted <-- false;
4. while !isSorted
5.	 isSorted = true; //assume list is sorted until told otherwise

6.	 while temp2.next != NULL //until we reach the end
//since the elems are Objects in the Java code, make sure they implement the Comparable interface
7.		 if temp.element > temp2.element  //if two elems are out of order
8.			  swap temp.element and temp2.element  //swap them
9.			  isSorted = false; //flag that the list isn't sorted
			end if
10.	   temp <-- temp.next //go to the next elements
11.	   temp2 <-- temp2.next
		 end while
end algorithm


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1