LOGIC:
1. Get a passed linked list -> 9, 3, 4, 12, 2, 5
2. Using the value of the head (9) of the passed linked list, create a new node , called CreatedHead
3. create a pointer node called runner which points to 2nd node of the passed linked list (3)
while (runner != null)
FIRST LOOP
Create a pointer node called arrow which points to the createdhead (9)
Create a pointer node called getNextNode which gets the 3rd node's address (4)
As 3 <= 9 (runner.value <= createdHead.value)
create a list by changing places:
3:9:null (exchange 1st and 2nd node)
getNextNode gets the 4th node's address (12)
runner = 4= getNextNode
2nd LOOP
(Bring the 3rd Node (4) and see)
Arrow = 3 = createdHead , getNextNode = 12 = runner.address;
As ( 4 > 3 ) runner.value > createdHead.value go to else
ELSE:::
2nd WHILE ::::::
As runner.value > Arrow.value ( 4>3) and && (4 < 9) runner.value <= Arrow.address.value
3:4:9:null (exchange 2nd and 3rd node)
Keep incrementing Arrow till null is encountered at 9
IF: skip If as runner.value (4) < Arrow.value (9)
runner = 12
3rd LOOP
(Bring the 4th Node 12 and see)
Arrow = 3 = createdHead , getNextNode = 2 = runner.address;
As ( 12 > 3 ) runner.value > createdHead.value
ELSE:::
2nd WHILE ::::::
As runner.value > Arrow.value ( 12>3) and && (12 > 4) runner.value > Arrow.address.value
Keep incrementing Arrow till null is encountered at 9 ( check all elements of the new list against 4th element to see if they are less than the 4th element (12).
- As 12 > 9 , so 12 is made the last elemnt of the new list having address of null , and 9's address points to it
3:4:9:12: null
4th LOOP
(Bring the 5th Node 2 and see)
Runner = 2
Arrow = 3 = createdHead , getNextNode = 5 = runner.address;
As 2 <= 3 (runner.value <= createdHead.value)
exchange 1st and 5th node
2:3:4:9:12:null
5th LOOP
Runner = 5
Arrow = 2 = createdHead , getNextNode = null = runner.address;
runner.value (5) > createdHead.value (2)
ELSE:::
2nd WHILE ::::::
10. As runner.value > Arrow.value ( 5 > 2 ) and && (5 > 3 ) runner.value > Arrow.address.value
12. Keep incrementing Arrow (move through the newly created list ) till
runner.value > Arrow.value ( 5 > 4 ) and && (5 <= 9 ) runner.value <= Arrow.address.value
- put 5 between 4 and 9
2:3:4:5:9:12:null
///////////////////////The Code///////////////////////////////////////////////////////////////////////////
class Node {
int value;
Node address;
Node(int X, Node Y) {
value = X;
address = Y;
}
}
public class Arrays {
public static Node sortInsertion(Node passedhead) {
//9, 3, 4, 12, 2, 5 - passed linked list . passed head == 9
if (passedhead == null || passedhead.address == null)
return passedhead;
//Create a new Node , having the passed head's value == 9, address as null
Node createdHead = new Node(passedhead.value , null);
//the runner Node points to second node, having value == 3
Node runner = passedhead.address;
while (runner != null) {
//In first while loop, Node Arrow points to createdHead
Node Arrow = createdHead;
Node getNextNode = runner.address;
if (runner.value <= createdHead.value)
{
//create a temporary node to store createdHead's address
//temp Node's value=9
Node temp = createdHead;
//createdHead.value=3
createdHead = runner;
//createdHead.address=Node having value 9
createdHead.address = temp;
}
else
{
while (Arrow.address != null)
{
if (runner.value > Arrow.value && runner.value <= Arrow.address.value)
{
Node temp = Arrow.address;
Arrow.address = runner;
runner.address = temp;
}
Arrow = Arrow.address;
}
if (Arrow.address == null && runner.value > Arrow.value)
{
Arrow.address = runner;
runner.address = null;
}
}
printL(createdHead);
runner = getNextNode;
}
return createdHead;
}
public static void main(String[] args) {
Node n1 = new Node(9,null);
Node n2 = new Node(3,null);
Node n3 = new Node(4,null);
Node n4 = new Node(12,null);
Node n5 = new Node(2,null);
Node n6 = new Node(5,null);
n1.address = n2;
n2.address = n3;
n3.address = n4;
n4.address = n5;
n5.address = n6;
n1 = sortInsertion(n1);
System.out.println("9, 3, 4, 12, 2, 5 - passed linked list ");
printL(n1);
}
public static void printL(Node head) {
if(head != null){
System.out.print(head.value + " ");
while (head.address != null) {
System.out.print(head.address.value + " ");
head = head.address;
}
System.out.println();
}
}
}
Copyright QA Friend Software Testing. All rights reserved.