Data Structures, Algorithms, & Applications in Java
Chapter 6, Exercise 23

BUBBLE SORT
The bubble sort code mimics the array-based code of Program 2.9. It may be modified to obtain an early-terminating version. The code is given below and in the file ChainWithSortMethods.java.

/** bubble largest element in first n nodes to right */
private void bubble(int n)
{
   ChainNode currentNode = firstNode;
   for (int i = 0; i < n - 1; i++)
   {
      ChainNode nextNode = currentNode.next;
      if (((Comparable) currentNode.element)
            .compareTo(nextNode.element) > 0)
      {// swap elements
         Object temp = currentNode.element;
         currentNode.element = nextNode.element;
         nextNode.element = temp;
      }
      currentNode = nextNode;
   }
}

/** sort the array a using the bubble sort method */
public void bubbleSort()
{
   for (int i = size; i > 1; i--)
      bubble(i);
}

Each bubbling pass takes Theta(i) time, where i is the number of nodes on the portion of the chain that is yet to be sorted. For an n node input chain, the time needed is Theta(n²). This is the asymptotic complexity for all data including initially sorted lists. There is some variability in the actual run time because the number of element swaps made in each bubbling pass varies.

SELECTION SORT
The code is very similar to Program 2.7. It is given below and in the file ChainWithSortMethods.java.

/** sort the chain using the selection sort method */
public void selectionSort()
{
   for (int i = size; i > 1; i--)
   {
      // find max object from first i nodes
      Comparable currentMax = (Comparable) firstNode.element;
      ChainNode maxNode = firstNode;
      ChainNode currentNode = firstNode;
      for (int j = 1; j < i; j++)
      {
         ChainNode nextNode = currentNode.next;
         if (currentMax.compareTo(nextNode.element) < 0)
         {// found a larger element
            currentMax = (Comparable) nextNode.element;
            maxNode = nextNode;
         }

         // move to next node
         currentNode = nextNode;
      }

      // move max object to right end
      maxNode.element = currentNode.element;
      currentNode.element = currentMax;
   }
}

Each selection pass takes Theta(i) time, where i is the number of nodes on the portion of the chain that is not known to be sorted. For an n node input chain, the time needed is Theta(n²).

RANK SORT
The code to compute the ranks is very similar to Program 2.5. The actual rearrangement is done by assigning the elements to bins according to their rank and then collecting the elements from the bins in rank order. The code is given below and in the file ChainWithSortMethods.java.

/** sort the chain using the rank sort method */
public void rankSort()
{
   if (size == 0)
      return;  // empty chain

   // r[i] will be rank of element i
   int [] r = new int [size];

   // compute ranks by comparing all pairs of elements
   ChainNode currentNode = firstNode;
   for (int i = 0; i < size; i++)
   {// compare currentNode.element with all elements
      ChainNode node = firstNode;
      for (int j = 0; j < i; j++)
      {// currentNode.element is element i and node.element
       // is element j, j < i
         if (((Comparable) node.element).compareTo
                                (currentNode.element) <= 0)
            r[i]++;
         else
            r[j]++;
         node = node.next;
      }
      currentNode = currentNode.next;
   }

   // distribute nodes to bins by rank
   ChainNode [] bin = new ChainNode [size];
   currentNode = firstNode;
   for (int i = 0; i < size; i++)
   {
      bin[r[i]] = currentNode;
      currentNode = currentNode.next;
   }

   // collect from bins
   firstNode = bin[0];
   ChainNode lastNode = firstNode;  // last node on chain
   for (int i = 1; i < size; i++)
      lastNode = lastNode.next = bin[i];
   lastNode.next = null;
}

For an n node input chain, the time taken to rank the elements is Theta(n²). The ensuing assignment and collection from bins takes Theta(n) time. Therefore, if an exception is not thrown, the complexity is Theta(n²).

Data Structures, Algorithms, & Applications in Java Chapter 6, Exercise 23

Data Structures, Algorithms, & Applications in Java
Chapter 6, Exercise 23