1.Given a linked list of integer elements, construct a SELECTION SORT algorithm that puts the integer elements into ascending order. Note that a selection sort does O(n) copies. On each pass, the smallest element is placed into its proper position. For example, on the third pass:
Before: 5 10 55 22 65 12 75
After : 5 10 12 22 65 55 75
The code should NOT re-link nodes - just copy elements. Do not create a new list.
Solution in java
class Node{
public int value;
public Node next;
public Node(int givenval){
value = givenval;
}
}
class List{
private int length;
private Node head;
private Node tail;
//adds a new node to the list with specified value
public void addtoList(int value){
Node node = new Node(value);
if(length ==0){
node.next = null;
}
else{
node.next = head;
}
head = node;
length++;
}
//prints contents of the list
public void Print(){
Node node = head;
while(node != null){
System.out.println(node.value);
node = node.next;
}
}
public void selectionSort(){
for(Node node1 = head; node1!=null; node1 = node1.next){//number of
//iterations
Node min = node1;//assumes min node is the node under considerations
//selects the min node
for(Node node2 = node1; node2!=null; node2 = node2.next){
if(min.value > node2.value){
min = node2;
}
}
//swaps the min node with the node in its actual position
Node temp = new Node(node1.value);
node1.value = min.value;
min.value = temp.value;
}
}
}
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
List list = new List();
list.addtoList(1);
list.addtoList(2);
list.addtoList(3);
list.addtoList(4);
list.addtoList(5);
System.out.println("Before sorting");
list.Print();
list.selectionSort();
System.out.println("After sorting");
list.Print();
}
}
This is perfect, but for the swapping you should probably try:
ReplyDeletepublic void selectionSort(){
for(Node node1 = head; node1!=null; node1 = node1.next){//number of
//iterations
Node min = node1;//assumes min node is the node under considerations
//selects the min node
for(Node node2 = node1; node2!=null; node2 = node2.next){
if(min.value > node2.value){
min = node2;
}
}
//swaps the min node with the node in its actual position
Node temp = new Node(node1.value);
node1.setValue(min.value);
min.setValue( temp.value);
since you want to set the value of node1 as the value at min and such
oggd one
ReplyDelete