Efficient sorting mechanism for Unsorted Array - List Insertion Sort

You can use sorted linked list as a sorting mechanism in some situations. Let us say you have an array of unsorted items. You copy items one by one from array and insert them one by one in to the sorted linked list. The end result is they all will be placed in sorted order automatically. This mechanism is called List Insertion Sort.

List Insertion Sort Example

package com.sneppets.dsalgo;

/**
 * Link
 */
class Link{
	//data
	public int intData;
	//next link in the list
	public Link next;
	//constructor
	public Link(int iData)
	{
		intData = iData;
	}
	//display link
	public void displayLink()
	{
		System.out.print(intData + " ");
	}
}

class SortedLinkedList{
	
	//reference to first link
	private Link first;
	
	//constructor
	public SortedLinkedList(Link[] linkArray)
	{
		//no links yet
		first = null;
		//copying array to list
		System.out.println("Copying array contents to newly created sorted linked list");
		for(int i=0; i<linkArray.length; i++)
		{
			insert(linkArray[i]);
		}
	}
	//return true if there are no links
	public boolean isEmpty()
	{
		return (first == null);
	}
	//logic to insert in order and insert() accepts Link object
	public void insert(Link link)
	{
		//set previous link to null, and use this null value to check whether you are at starting of the list
		Link prevLink = null;
		//set current link to first
		Link curLink = first;
		//until end of list is reached or if int data of the link being inserted is greater than the int data that is currently being examined
		while (curLink != null && link.intData > curLink.intData)
		{
			prevLink = curLink;
			//go to next item in the list
			curLink = curLink.next;
		}		
		if(prevLink == null)
		{	//if at the beginning of the list or the list is empty, then set first --> link
			first = link;
		}
		else
		{	//if not at the beginning of the list, then set old prevLink --> newLink
			prevLink.next = link;
		}
		//newLink --> old current
		link.next = curLink;			
	}
	
	//return and delete first link
	public Link deleteFirst()
	{
		//save first link
		Link temp = first;
		//delete first link
		first = first.next;
		//return first link
		return temp;		
	}
	
	public void displayList()
	{
		System.out.println("List (Sorted) from first to last :");
		//start from beginning of the list
		Link curLink = first;
		//until end of list is reached
		while (curLink != null)
		{
			//print link details
			curLink.displayLink();
			//move to next link
			curLink = curLink.next;
		}
		System.out.println(" ");
	}
}

/**
 * 
 * @author sneppets.com
 *
 */
public class SortedLinkedListInsertionSortExample {
	
	public static void main(String[] args)
	{
		int arraySize = 5;
		//create array of links
		Link[] linkArray = new Link[arraySize];
		
		//fill link array with links
		Link newLink = new Link(20);
		linkArray[0] = newLink;
		
		newLink = new Link(50);
		linkArray[1] = newLink;
		
		newLink = new Link(30);
		linkArray[2] = newLink;
		
		newLink = new Link(40);
		linkArray[3] = newLink;
		
		newLink = new Link(10);
		linkArray[4] = newLink;
		//display unsorted array items
		System.out.println("Displaying link array contents - Unsorted array");
		for (int i=0; i<arraySize; i++)
		{
			System.out.print(linkArray[i].intData+ " ");
		}
		System.out.println(" ");
		
		//create new sorted linked list initialized with array
		SortedLinkedList sortedLinkedList = new SortedLinkedList(linkArray);
		
		//display list items 
		System.out.println("Displaying sorted linked list contents");
		sortedLinkedList.displayList();
		
		//copy links from list to array		
		System.out.println("Removed links from sorted linked list one by one and returned/copied links from list to array");
		for(int i=0; i<arraySize; i++)
		{
			linkArray[i] = sortedLinkedList.deleteFirst();
		}
		System.out.println("Displaying link array contents - Sorted array");		
		for(int i=0; i<arraySize; i++)
		{
			System.out.print(linkArray[i].intData+ " ");
		}
		System.out.println(" ");
	}

}

Note: insert() method accepts a Link object as an argument. So that we can store Link objects in the array and directly insert them in to the sorted linked list.

Output:

Displaying link array contents - Unsorted array
20 50 30 40 10  
Copying array contents to newly created sorted linked list
Displaying sorted linked list contents
List (Sorted) from first to last :
10 20 30 40 50  
Removed links from sorted linked list one by one and returned/copied links from list to array
Displaying link array contents - Sorted array
10 20 30 40 50

Efficiency of List Insertion Sort

This type of sorting mechanism is more efficient than Simple Sorting (Insertion sort within an array) because only fewer copies are necessary in this case i.e., N copies (for items that are copied only once from array to the list) and one more N copies (for items that are copied only once from list to the array). So total N*2 copies compared to insertion sort within an array, where it requires N² copies.

Drawbacks of list insertion sort

The drawback of list insertion sort is it takes somewhat more than twice as much memory than the array-based insertion sort. The array and linked list must be in memory at the same time.

List Insertion Sort Example

Efficiency of List Insertion Sort

Drawbacks of list insertion sort

Recommended Posts

References