Insertion sort using a linked list is a variant as we can avoid having to make a series of swaps for each insertion, the input could be stored in a linked list, which allows elements to be inserted and deleted in constant-time.

Each element is copied from array to list and then back to array so there are 2N copies of elements but if we were to do insertion sort in place in the array then there would be N^{2} copies.

Although this variant reduces runtime with regards to copies, it is still a O(N^{2}) algorithm as each item is inserted into the list and is compared with at least half the elements in the list already present with N items in total to insert.

In essence performing a binary search on a linked list is impractical because random access is not directly supported by a linked list and can only be effectively achieved by sequentially following the link chain to each desired element, which is relatively very slow; therefore, the running time required for searching is O(n^{2}) – Wikipedia

so total run time = O(n^{2})[searching] + 2n [copies]

class Node
{
public int item;
public Node next;
public Node(int val)
{
item = val;
}
}
class InsSort
{
private Node first;
public InsSort()
{ first = null; }
public InsSort(Node[] linkArr)
{
first = null;;
for(int j=0; j<linkArr.length; j++)
insert( linkArr[j] );
}
public void insert(Node k)
{
Node previous = null;
Node current = first;
while(current != null && k.item > current.item)
{
previous = current;
current = current.next;
}
if(previous==null)
first = k;
else
previous.next = k;
k.next = current;
}
public Node pop()
{
Node temp = first;
first = first.next;
return temp;
}
}
class InsSortListBlog
{
public static void main(String[] args)
{
int size = 10;
Node[] linkArray = new Node[size];
for(int j=0; j<size; j++)
{
int n = (int)(java.lang.Math.random()*99);
Node newLink = new Node(n);
linkArray[j] = newLink;
}
System.out.print("Input unsorted array: ");
for(int j=0; j<size; j++)
System.out.print( linkArray[j].item + " " );
System.out.println("");
InsSort theInsSort = new InsSort(linkArray);
for(int j=0; j<size; j++)
linkArray[j] = theInsSort.pop();
System.out.print("sorted array: ");
for(int j=0; j<size; j++)
System.out.print(linkArray[j].item + " ");
System.out.println("");
}
}

OUTPUT:

labuser@ubuntu:~/InsSortList$ java InsSortListBlog

Input unsorted array: 82 8 87 29 73 86 96 15 91 44

sorted array: 8 15 29 44 73 82 86 87 91 96

labuser@ubuntu:~/InsSortList$

### Like this:

Like Loading...

*Related*