Tuesday, June 23, 2009

Selection sort of Linked List ( Java)

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();

}

}

2 comments:

  1. This is perfect, but for the swapping you should probably try:

    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.setValue(min.value);
    min.setValue( temp.value);

    since you want to set the value of node1 as the value at min and such

    ReplyDelete