In selection sorting (in increasing order) an array, we repeatedly locate the sm

Question

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 timeconsuming 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 in milliseconds. (Use System.currentTimeMillis() before and after call to sort(). The difference is the time spent on sorting).

Output Asgn04_Key Alt (run) & run: CPS 151 Assignment 4 by KEY Demonstrate Sorting Original list ?! [765, 786, 394, 377, 565, 96, 718, 192, 875, 167] Sorted list [96, 167, 192, 377, 394, 565, 718, 765, 786, 875] List size vs. Selection sort timing List Size Time (msec) 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 167 637 1334 2361 3390 5281 6928 9473 11020 14718 Assignment 4 complete BUILD SUCCESSFUL (total time: 57 seconds)

Explanation / Answer

Given below is the code for the question. By the way, the code was not compiling with all out.println() lines. So I had to change them to System.out.println()
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
Please do rate the answer if it was helpful. Thank you

import java.util.NoSuchElementException;
import java.util.Random;

public class Asgn04 {
static final Random rand = new Random();

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
System.out.println("CPS 151 Assignment 4 by your name here ");
demoSelectionSort();
displayTable();
System.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 <= count; Lcv++)
L.addFirst(rand.nextInt(range));
} // end method
  
private static void demoSelectionSort() {
System.out.println("Demonstrate Sorting");
System.out.println("-------------------");
SortableList L = new SortableList();
loadRandom(L, 10, 1000);
System.out.println("Original list " + L);
L.sort();
System.out.println(" Sorted list " + L);
} // end method

private static void displayTable() {
// creating the table
long beginAt, endAt; // for recording system times
  
// print table heading
System.out.println("List size vs Selection sort timing");
System.out.println("==================================");
  
System.out.printf("%10s %12s ", "List Size", "Time (msec)");
// Complete the loop body to create and print the table data
for (int size = 10000; size <= 100000; size += 10000) {
beginAt = System.currentTimeMillis();
SortableList L = new SortableList();
loadRandom(L, size, 1000);
L.sort();
endAt = System.currentTimeMillis();
System.out.printf("%10d %12d ", size, endAt - beginAt);

} // end loop
  
System.out.println();
} // end method
  
} // end main class

// ------------ class IntLinkedList DO NOT MODIFY THIS CLASS
class IntLinkedList {

protected Node head; // allow subclass to access it directly

public IntLinkedList() {
head = null;
} // end constructor

public boolean isEmpty() {
return this.head == null;
} // end isEmpty

public int size() {
int count = 0;

Node cur = head;

while (cur != null) {
cur = cur.next;
count++;
} // end loop

return count;
} // end size

public void addFirst(int element) {  
head = new Node(element, head);
} // end addFirst

public int removeFirst() throws NoSuchElementException {
if (head == null)
throw new NoSuchElementException("List empty, cannot remove");

int result = head.data;
head = head.next;

return result;
} // end removeFirst

@Override
public String toString() {
String value = "[";
Node cur = this.head;

while (cur != null) {
value = value + cur.data;
cur = cur.next;
if (cur != null)
value = value + ", ";
} // end loop
return value + "]";
} // end toString

} // end class

// ------------ class SortableLinkedList
class SortableList extends IntLinkedList {
  
private int removeMax() throws NoSuchElementException {
if (head == null)
throw new NoSuchElementException("List empty, cannot remove");

// declare variables needed (will need to add more)
Node prev = null, cur = head;
Node maxNode = head, prev2Max = null;

// write the loop to locate the node containing largest value
while(cur != null)
{
if(cur.data > maxNode.data)
{
//save the max and previous node to the maximum node
prev2Max = prev;
maxNode = cur;
}
prev = cur;
cur = cur.next;
}
// remove the node containing the largest value
// special case: head reference needs to change when?
if(maxNode == head)
head = maxNode.next;
else
prev2Max.next = maxNode.next;
return maxNode.data;
} // end removeMax

public void sort() {
if (head == null || head.next == null) return; // already sorted

SortableList tempList = new SortableList();

// Write the sorting loop as discussed
while(!isEmpty())
{
tempList.addFirst(removeMax());
}

// adjust references to make "this" list be the sorted list
this.head = tempList.head;

} // end sort
  
} // end class

//--------------- class Node DO NOT MODIFY THIS CLASS

class Node {
public int data;
public Node next;
  
// constructor 1
public Node(int data) {
this(data, null);
}
  
// constructor 2
public Node(int data, Node next) {
this.data = data; this.next = next;
}
} // end class

output
------
CPS 151 Assignment 4 by your name here

Demonstrate Sorting
-------------------
Original list
[276, 837, 734, 570, 898, 91, 436, 646, 338, 669]

Sorted list
[91, 276, 338, 436, 570, 646, 669, 734, 837, 898]
List size vs Selection sort timing
==================================
List Size Time (msec)
10000 215
20000 907
30000 1940
40000 3509
50000 5580
60000 8171
70000 11296
80000 16106
90000 22311
100000 32166

Assignment 4 complete

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.