Part 1) Recall the algorithm for Selection Sort: step 1) find the min value in t
ID: 673587 • Letter: P
Question
Part 1)
Recall the algorithm for Selection Sort:
step 1) find the min value in the unsorted subset
step 2) Move that value into the 1st location of the unsorted subset
repeat these 2 steps n-1 times (where n is the size of the original set of unsorted values)
For this assignment, you will create a program that will perform this algorithm on an unsorted LinkedList2 object. LinkedList2 is the class that used Node2 objects that had pointers to go both to next and previous. (***HINT*** In order to generate an unsorted list for your own testing purposes, use the append method instead of the insert method. The append method is NOT in class LinkedList2 on blackboard. You will have to create it or copy it from the original class LinkedList) Create methods "move" and "findMin" in class LinkedList2 according to the requirements listed below. Create a main method in class Assignment4 according to the requirements listed below.
a) Create a method called "findMin" that will start searching the list from the node passed as a parameter until the end of the list. DO NOT search the list from the head node. The method should return the node with the smallest int value. DO NOT return the int.
b) Create a method called "move" that will take in 2 node objects as parameters. You may assume that the 2 nodes both exist in the same list and you may assume that the 2 parameters are not pointing to the same node. The method should remove the node of the first parameter from its current location in the list and then re-insert it into the list immediately before the node of the second parameter.
c) Create a main method that repeatedly (n-1 times) calls method findMin and then take the node returned from that method and by using method move, moves the node returned from findMin before the 1st location of the unsorted part of the list, (**NOTE** this is not swapping values like we did with arrays, it is behaving slightly differently). BEFORE calling method move, check to see if the node returned from the findMin method is already in the first location of the unsorted portion of the list. If it is, DO NOT call method move.
I strongly recommend that you perform your own testing to ensure that this algorithm behaves like you intend. Generate a list of unsorted numbers and then run the main method to sort them. Check for boundary cases. For example, if the min node is at one of the extremes of the list or if the min node is the 1st node in the unsorted portion, etc. Do not show me or submit your testing.
Part 2)
a) Create a method in class LinkedList2 called sum. This method should traverse (travel through) the entire list from the head until the end and add up all of the data values and return the sum of all of the data values of the nodes in the list.
b) in the main method in class Assignment4 (yes, the same main method as in part 1) create 3 different LinkedList2 objects. One of them could be the same as what you created in part 1. Each list should have at least 5 nodes. Find the sum of the data elements of the nodes in each of the 3 lists. You should have 3 different sums, one for each list. Output using a JOptionPane which list has the largest sum.
Explanation / Answer
// File: LinkedList2.java
public class LinkedList2
{
private class Node2
{
private int value;
private Node2 next;
private Node2 prev;
public Node2(int aValue)
{
value = aValue;
next = null;
prev = null;
}
}
private Node2 head;
private int count;
public LinkedList2()
{
head = null;
count = 0;
}
public Node2 search(int aValue)
{
Node2 current = head;
while(current != head)
{
if(current.value == aValue)
return current;
current = current.next;
}
return null;
}
public void append(int aValue)
{
Node2 newNode = new Node2(aValue);
if(head == null)
{
head = newNode;
}
else
{
Node2 curr = head;
while(curr.next != null)
curr = curr.next;
}
count++;
}
public Node2 remove(int item)
{
Node2 removed = null;
if(isEmpty())
return null;
Node2 pntr = head;
Node2 temp = null;
while(pntr != head && item != pntr.value)
{
temp = temp.next;
pntr = pntr.next;
}
while(pntr != head && item == pntr.value)
{
removed = pntr;
count--;
if(temp == null)
{
head.next = pntr.next;
pntr.next = head;
}
else
{
temp.next = pntr.next;
pntr.next = temp;
}
}
return removed;
}
public boolean isEmpty()
{
return (count == 0);
}
public int size()
{
return count;
}
public void printForward()
{
System.out.print("Forward List: ");
Node2 current = head;
while(current != null)
{
System.out.print(current.value + " ");
current = current.next;
}
System.out.println();
}
}