public class Asgn04 { static final Random rand = new Random(); /** * @param args the command line arguments */ public static void main(String[] args) { out.println("CPS 151 Assignment 4 by your name here "); demoSelectionSort(); displayTable(); out.println(" Assignment 4 complete"); } // end main // loads random values into initialized IntLinkedList L static void loadRandom(final IntLinkedList L, final int count, final int range) { for (int Lcv = 1; Lcv  
  In selection sorting (in increasing order) an array, we repeatedly locate the smallest value in the unsorted portion of the array and swap it in its proper position in the array. How can we implement the Selection sort for a linked list? As you have seen, with a linked list it is easy to add a new Node at the beginning. Adding a new Node at the end is either time consuming or requires maintaining an extra reference to the last node. To avoid that, we adopt this strategy: Say we have a list L. To sort it, we create another empty list (say L2). We repeatedly remove the largest value from L and add it at the beginning of L2. Eventually L becomes empty and L2 contains all the data in increasing order. Now we can make L's head node reference a copy of L2's head node reference and L will be the sorted list. [L2's head node reference should be changed to null] We start with a class IntLinkedList. This class should not be modified. The class SortableList inherits from IntLinkedList and adds methods removemax () and sort () How to implement removeMax() You will need to walk through the linked list maintaining references to two nodes. The node we are looking at now and the node known to contain the largest value seen so far. Remember that to be able to remove a node we also need to know which node is just before the node to be removed. There is the usual special case of removing the head node The client should show sorting works for a small random linked list. Then it should create random lists of large sizes (say 10,000 to 100,000 in steps of 10, 000). The client should produce a table of list sizes and corresponding sorting times irn milliseconds. (Use System.currentTimeMillis ) before and after call to sort ().The difference is the time n sorting). These are the results I got from my program. Different runs do tend to give different results  In selection sorting (in increasing order) an array, we repeatedly locate the smallest value in the unsorted portion of the array and swap it in its proper position in the array. How can we implement the Selection sort for a linked list? As you have seen, with a linked list it is easy to add a new Node at the beginning. Adding a new Node at the end is either time consuming or requires maintaining an extra reference to the last node. To avoid that, we adopt this strategy: Say we have a list L. To sort it, we create another empty list (say L2). We repeatedly remove the largest value from L and add it at the beginning of L2. Eventually L becomes empty and L2 contains all the data in increasing order. Now we can make L's head node reference a copy of L2's head node reference and L will be the sorted list. [L2's head node reference should be changed to null] We start with a class IntLinkedList. This class should not be modified. The class SortableList inherits from IntLinkedList and adds methods removemax () and sort () How to implement removeMax() You will need to walk through the linked list maintaining references to two nodes. The node we are looking at now and the node known to contain the largest value seen so far. Remember that to be able to remove a node we also need to know which node is just before the node to be removed. There is the usual special case of removing the head node The client should show sorting works for a small random linked list. Then it should create random lists of large sizes (say 10,000 to 100,000 in steps of 10, 000). The client should produce a table of list sizes and corresponding sorting times irn milliseconds. (Use System.currentTimeMillis ) before and after call to sort ().The difference is the time n sorting). These are the results I got from my program. Different runs do tend to give different results