Sorting Elements in a Singly Linked Data Structure

Sorting Elements in a Singly Linked Data Structure

Override class Object’s toString to return one string that concatenates the toString version of each element followed by one blank space. Also add method sort to classSortableList(show below) to arrange all elements into their natural ordering. Only Comparable objects can be added, so there is no need to cast elements to Comparable. Here are the method headings:

public String toString()// Return toString of elements with blank separators

publicvoidsort(E element) // Arrange elements into their natural Ordering

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

@Test

public void testSort() {

SortableList<String> sl = new SortableList<String>();

sl.addFirst("June");

sl.addFirst("Matty");

sl.addFirst("Alma");

sl.addFirst("Zeke");

assertEquals("Zeke Alma Matty June ", s1.toString());

sl.sort();

assertEquals("Alma June Matty Zeke ", s1.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 LinkNode objects from top through the second to last ("Alma" below)

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

(c) for inner referencing LinkNodetop.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)

After one iteration, “Alma” is in the correct place

Let top refer to the 2nd element and repeat one swap ….

Assignment 9: SortableList Methods. In teams of exactly two, complete methods toString and sort. Each person write one method.

1) Scribe to write toString ______

2) Scribe to write sort ______

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

privateclass Node {

private E data;

private Node next;

public Node(E objectReference, Node nextReference) {

data = objectReference;

next = nextReference;

}

} // end class Node

private Node first;

1) Complete toString as a method inside class, both with access to first. (8pts)

public String toString() {

2) Complete sort as a method inside this class, with access to first. (16pts)

publicvoidsort() {