Sorting elements in a Singly Linked Structure (Summer 2010)
Goal: Write methods using linked structures: toString() and sort() in class GenericList
// Return a textual representation of all elements
// separated by ", " and surrounded by []
public String toString()
// Arrange all elements in their natural (ascending) order.
// GenericList<E> assumes the type of elements implement Comparble<T>
public void sort()
public class GenericList<E> implements LittleList<E> {
private class Node {
private E data;
private Node next;
public Node(E objectReference, Node nextReference) {
data = objectReference;
next = nextReference;
}
} // end the inner Node class
private Node first;
private inte n;
public GenericList() {
first = null;
n = 0;
}
public void addFirst(E element) {
first = new Node(element, first);
}
toString()
As a class, let's do toString together
@Test
public void testToString() {
GenericList<String> list = newGenericList<String>();
assertEquals("[]", list.toString());
list.addFirst("June");
list.addFirst("Matty");
list.addFirst("Alma");
list.addFirst("Zeke");
assertEquals("[Zeke, Alma, Matty, June]", list.toString());
list.sort();
assertEquals("[Alma, June, Matty, Zeke]", list.toString());
}
sort()
- Demonstrate Selection sort with five volunteers
- Consider the selection sort algorithm given as steps (a), (b), (c), and (d) below. Steps (b), and (c) find a reference to the node with the "smallest" data in the list. Step (d) swaps the data elements the data in the first node. Step (a) makes sure that done n-2 swaps are made. Assume the list has at least 2 elements.
@Test
public void testToString () {
GenericList<String> list = newGenericList<String>();
list.addFirst("June");
list.addFirst("Matty");
list.addFirst("Alma");
list.addFirst("Zeke");
assertEquals("[Zeke, Alma, Matty, June]", list.toString());
list.sort();
assertEquals("[Alma, June, Matty, Zeke]", list.toString());
}
- In teams of 2, write the sort method on a separate piece of paper as if it were a method inside GenericList.
Selection Sort algorithm for a singly linked structure
(a)let left reference all Node objects from the first through the second to last ("Alma" below)
(b)smallestRef = left // At first, assume that the first element is the smallest
(c)for inner referencing Nodeleft.next through the last Node // Check the rest of the list
if inner.data < smallestRef.data
smallestRef = inner
(d)Swap left.data with smallestRef.data (list is sorted up to left)