Data Structures, Algorithms, & Applications in C++
Chapter 7, Exercise 1

The selection sort code for simulated chains is very similar to Program 2.7. It is given below and in the file SimulatedChainWithSelectionSort.java. 
public class SimulatedChainWithSelectionSort extends SimulatedChain
{
   /** 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) S.node[firstNode].element;
         int maxNode = firstNode;
         int currentNode = firstNode;
         for (int j = 1; j < i; j++)
         {
            int nextNode = S.node[currentNode].next;
            if (currentMax.compareTo(S.node[nextNode].element) < 0)
            {// found a larger element
               currentMax = (Comparable) S.node[nextNode].element;
               maxNode = nextNode;
            }

            // move to next node
            currentNode = nextNode;
         }

         // move max object to right end
         S.node[maxNode].element = S.node[currentNode].element;
         S.node[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(n2).