Java RSS Java RSS

Bubble Sort in Linked List- Help Greatly Appreciated

Reply

•
•
Join Date: Nov 2007
Posts: 1
Reputation: huntatunc is an unknown quantity at this point 
Solved Threads: 0
huntatunc huntatunc is offline Offline
Newbie Poster

Bubble Sort in Linked List- Help Greatly Appreciated

 
0
  #1
Nov 15th, 2007
so, everything works through the first iteration (don't know if this is an appropriate term for linked lists, but we just learned arrays) but then it stops. I thought that telling it to continue until position.next != null and increasing the position after every iteration would work but I think I have coded something incorrectly / am not taking something into consideration. I would be greatly obliged if you can offer any advice!

I had one more question I wanted to ask...

I am also writing a method called insertionSort (using insertion sort to sort a linked list). Anyway, I know in an array, you copy the item into a temporary space and then insert it into the sorted list in its appropriate place. I am wondering how I create such a space as with bubble sort my temp. space was merely incorporated as the next node.

Thanks,
Hunter

Java Syntax (Toggle Plain Text) 
  1.     public class LinkedList
  2.    {
  3.  
  4.       public Node head;
  5.  
  6.        public LinkedList(int length)
  7.       {
  8.          head = null;
  9.  
  10.          for (int i = 0; i < length; i ++)
  11.             insert(i);
  12.  
  13.       }
  14.  
  15.        public LinkedList()
  16.       {
  17.          head = null;
  18.       }
  19.  
  20.        public void clear()
  21.       {
  22.          head = null;
  23.       }
  24.  
  25.        public void insert(int n)
  26.       {
  27.          Node current = new Node(n);
  28.  
  29.          current.next = head;
  30.  
  31.          head = current;
  32.       }
  33.  
  34.        public void insert(Node n, int index)
  35.       {
  36.          Node previous, current;
  37.  
  38.          Node nnode = new Node(-10);
  39.          nnode.next = head;
  40.  
  41.          previous = nnode;
  42.          current = head;
  43.  
  44.          while (current != null && index > 0)
  45.          {
  46.             current = current.next;
  47.             previous = previous.next;
  48.             index --;
  49.          }
  50.  
  51.          if (previous == nnode)
  52.          {
  53.             n.next = head;
  54.             head = n;
  55.          }
  56.          else
  57.          {
  58.             previous.next = n;
  59.             n.next = current;
  60.          }
  61.       }
  62.  
  63.  
  64.        public void delete(int index)
  65.       {
  66.          int current;
  67.          Node currentnode = head;
  68.  
  69.          for (current = index; current > 1; current --) 
  70.             currentnode = currentnode.next;
  71.  
  72.          if (currentnode == head)
  73.             head = head.next;
  74.          else
  75.             currentnode.next = currentnode.next.next;
  76.       }
  77.  
  78.        public Node getNode(int index)
  79.       {
  80.          Node nnode = new Node(-10);
  81.          nnode.next = head;
  82.  
  83.          Node current = head;
  84.          while(current.next != null && index > 0)
  85.          {	current = current.next;
  86.             index --;
  87.  
  88.          }
  89.  
  90.          return current;
  91.       }
  92.  
  93.        public int getVal(int index)
  94.       {
  95.          int current;
  96.          Node currentnode = head;
  97.  
  98.          for (current = index; current > 0; current --) 
  99.             currentnode = currentnode.next;
  100.  
  101.  
  102.          return currentnode.getVal();
  103.       }
  104.  
  105.        public void print()
  106.       {
  107.          System.out.println();
  108.  
  109.          head.print();
  110.       }
  111.  
  112.        private void swap(Node pa, Node a, Node pb, Node b)
  113.       {
  114.          Node temp = b.next;
  115.          pa.next = b;
  116.          if (a.next != b)
  117.          {
  118.             b.next = a.next;
  119.             pb.next = a;
  120.          }
  121.          else
  122.             b.next = a;
  123.  
  124.          a.next = temp;
  125.       }
  126.  
  127.        public void selectionSort()
  128.       {
  129.          Node current, a, previous, position;
  130.          position = new Node(0);
  131.          position.next = head;
  132.          head = position;
  133.  
  134.          while (position.next  != null)
  135.          {	
  136.             current = previous = position.next;
  137.             a = position.next;
  138.             while(a != null)
  139.             {
  140.                if (a.getVal() < current.getVal())
  141.                {
  142.                   current = a;
  143.                   while(previous.next != current)
  144.                      previous = previous.next;
  145.                }
  146.                a = a.next;
  147.             }
  148.  
  149.             if (current != previous)
  150.             {
  151.                Node t = position.next;
  152.                swap(position, t, previous, current);
  153.             }
  154.             position = position.next;
  155.          }
  156.          head = head.next;
  157.       }
  158.  
  159.       public void bubbleSort()
  160.       {
  161.          Node current, a, previous, position;
  162.          position = new Node(0);
  163.          position.next = head;
  164.          head = position;
  165.  
  166.          while (position.next != null)
  167.          {  current = position.next;
  168.           previous = position;
  169.             a = current.next;
  170.             while(a != null)
  171.             {
  172.                if (a.getVal() < current.getVal())
  173.                {
  174.                   Node temp = a.next;
  175.                   a.next = previous.next;
  176.                   previous.next = current.next;
  177.                   current.next = temp; 
  178.  
  179. 	previous = a;
  180. 	a = temp;
  181.                }
  182.                 else
  183.                   {
  184. 	a = a.next;
  185.                  current = current.next;
  186. 	previous = previous.next;
  187. 	}
  188.  
  189.             }	
  190.              position = position.next;
  191.          }
  192.          head = head.next;
  193.       }
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2006
Posts: 101
Reputation: cms271828 is an unknown quantity at this point 
Solved Threads: 4
cms271828 cms271828 is offline Offline
Junior Poster

Re: Bubble Sort in Linked List- Help Greatly Appreciated

 
0
  #2
Nov 16th, 2007
Its simple, I don't see the point for all that code, and I'm not sure why your class is called LinkedList, theres already a LinkedList in the java.util package.
I've just written the code below, might be a couple of bugs in it, I haven't tested it, but thats how I would do it.

Java Syntax (Toggle Plain Text) 
  1. import java.util.*;
  2.  
  3. public class BubbleSort
  4. {
  5.     public static void main(String[] args)
  6.     {
  7.          LinkedList items=new LinkedList();
  8.          // add all Integer elements to items
  9.  
  10.          bubbleSort(items);
  11.     }
  12.  
  13.     public void bubbleSort(LinkedList items)
  14.     {
  15.          for(int sort=1;sort<items.getSize();sort++)
  16.          {
  17.              singleSort(items);
  18.          }
  19.     }
  20.  
  21.     public void singleSort(LinkedList  items)
  22.     {
  23.         for(int item=0;item<items.getSize()-1;item++)
  24.         {
  25.              Integer left=(Integer)items.get(item);
  26.              Integer right=(Integer)items.get(item+1);
  27.  
  28.             if(left.intValue() > right.intValue()) swap(items, item+1);
  29.         }
  30.     }
  31.  
  32.     public void swap(LinkedList items,int right_index)
  33.     {
  34.          Integer right=items.remove(right_index);
  35.          items.add(right_index-1,right);
  36.     }
  37. }

In fact, there is a sort method available that you can use, I think you need to use comparator, or comparable, but from a developers view point, thats how you would sort a collection.
Last edited by cms271828; Nov 16th, 2007 at 1:38 pm. Reason: Additional Information
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the Java Forum
Thread Tools Search this Thread



-xlint add android api applet application array arrays automation bi binary blackberry block bluetooth class client code compile compiler component database developmenthelp eclipse equation error event fractal freeze functiontesting game gameprogramming givemetehcodez graphics gui health html hyper ide idea image int integer j2me j2seprojects java javac javaprojects jetbrains jni jpanel jtable julia learningresources lego linux list login loops mac main map method methods mobile myregfun netbeans nonstatic notdisplaying number online pearl problem program project qt recursion scanner screen server set singleton sms sort spamblocker sql string swing system textfields thread threads time title tree tutorial-sample update variablebinding windows working xor
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC