Sorting Elements in a Singly Linked Data Structure

Sorting Elements in a Singly Linked Data Structure

Recommended Activities:

1. Questions on Assignment?
2. Questions on Project?
3. Consider SortableList and addFirst (see usage in test method below)
4. Section leader describes selection sort algorithm for a singly linked structure on whiteboard
5. In teams of 2 or 3, implement the sort algorithm in Java using Node objects with data and next
6. If time permits, one team adds sort()to SortableList to see if the tests below pass.

Add method sort to class SortableList (shown below) to arrange all elements into their natural ordering. Assume only Comparable objects can be added, so there is no need to cast to Comparable. Here is the method heading:

public void sort(E element) // Arrange elements into their natural Ordering

// use the compareTo method of type E

The following test method shows the effect of sort on the order of elements

@Test

public void testSortOnListOfStrings() {

SortableList<String> list = new SortableList<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());

}

@Test

public void testSortOnListOfInts() {

SortableList<Integer> list = new SortableList<Integer>();

assertEquals("[]", list.toString());

list.addFirst(4);

assertEquals("[4]", list.toString());

list.addFirst(6);

assertEquals("[6, 4]", list.toString());

list.addFirst(-2);

list.addFirst(8);

assertEquals("[8, -2, 6, 4]", list.toString());

list.sort();

assertEquals("[-2, 4, 6, 8]", list.toString());

}

Use the selection sort algorithm pictured below in steps (a), (b), (c), and (d). Steps (b), and (c) find a reference to the node with the "smallest" data in the list. Step (d) swaps the smallest node's data with the data in the node reference as top. Step (a) makes sure that done n-2 swaps are made. Assume the list has at least 2 elements.

Algorithm to Selection Sort Elements Stored in a Singly Linked Structure

(a) let top reference all Node objects from top through the second to last Node

(b) smallestRef = top // At first, assume that the first element is the smallest

(c) for inner referencing LinkNode top.next through the last LinkNode // Check rest of list

if inner.data < smallestRef.data

smallestRef = inner

(d) Swap top.data with smallestRef.data (list is sorted up through top)

// Note: After one iteration, "Alma" is in the correct place

go to (a)

In teams of two or three, add method sort to SortableList.

// The type parameter here ensures types are limited to any type that implements

// interface Comparable<E> or another interface that extends Comparable<E>.

// Yes, you can have MyComparable extends Comparable, any class must have compareTo

public class SortableList<E extends Comparable <E> { // Use compareTo on any E

private class Node {

private E data;

private Node next;

public Node(E objectReference, Node nextReference) {

data = objectReference;

next = nextReference;

}

} // end class Node

private Node first;

public void addFirst(E element) {

first = new Node(element, first);

}

public String toString() {

String result = "[";

for (Node p = first; p != null; p = p.next) {

result += p.data + ", ";

}

if (first != null)

result = result.substring(0, result.length() - 2);

return result + "]";

}

public void sort() {

} // end method SorT

} // end class SortableList