Would sorting a linked list improve the time it takes to nd an element in the list?

An In-Depth Look At Insertion Sort With Classic Examples.

Insertion sort is a sorting technique which can be viewed in a way which we play cards at hand. The way we insert any card in a deck or remove it, insertion sorts works in a similar way.

Insertion sort algorithm technique is more efficient than the Bubble sort and Selection sort techniques but is less efficient than the other techniques like Quicksort and Merge sort.

=> Check Out The Best C++ Training Tutorials Here.

Overview

In the insertion sort technique, we start from the second element and compare it with the first element and put it in a proper place. Then we perform this process for the subsequent elements.

We compare each element with all its previous elements and put or insert the element in its proper position. Insertion sort technique is more feasible for arrays with a smaller number of elements. It is also useful for sorting linked lists.

Linked lists have a pointer to the next element (in case of a singly linked list) and a pointer to the previous element as well (in case of a doubly linked list). Hence it becomes easier to implement insertion sort for a linked list.

Let us explore all about Insertion sort in this tutorial.

General Algorithm

Step 1: Repeat Steps 2 to 5 for K = 1 to N-1
Step 2: set temp = A[K]
Step 3: set J = K 1
Step 4: Repeat while temp <=A[J]
set A[J + 1] = A[J]
set J = J 1
[end of inner loop]
Step 5: set A[J + 1] = temp
[end of loop]
Step 6: exit

Thus, in the insertion sort technique, we start from the second element as we assume that the first element is always sorted. Then from the second element to the last element, we compare each element to all of its previous elements and the put that element in the proper position.

Pseudocode

The pseudo code for insertion sort is given below.

procedure insertionSort(array,N ) array array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element whilefreePosition> 0 and array[freePosition -1] >insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert the number at free position array [freePosition] = insert_val end for end procedure

Given above is the pseudo code for Insertion sort, next, we will illustrate this technique in the following example.

Illustration

The array to be sorted is as follows:

Now for each pass, we compare the current element to all its previous elements. So in the first pass, we start with the second element.

Thus we require N number of passes to completely sort an array containing N number of elements.

The above illustration can be summarized in a tabular form:

As shown in the above illustration, we begin with the 2nd element as we assume that the first element is always sorted. So we begin with comparing the second element with the first one and swap the position if the second element is less than the first.

This comparison and swapping process positions two elements in their proper places. Next, we compare the third element to its previous (first and second) elements and perform the same procedure to place the third element in the proper place.

In this manner, for each pass, we place one element in its place. For the first pass, we place the second element in its place. Thus in general, to place N elements in their proper place, we need N-1 passes.

Next, we will demonstrate the Insertion sort technique implementation in C++ language.

C++ Example

#include<iostream> using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<"\nInput list is \n"; for(int i=0;i<10;i++) { cout <<myarray[i]<<"\t"; } for(int k=1; k<10; k++) { int temp = myarray[k]; int j= k-1; while(j>=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } cout<<"\nSorted list is \n"; for(int i=0;i<10;i++) { cout <<myarray[i]<<"\t"; } }

Output:

Inputlistis

1243115453321102

Sortedlistis

1234101215213345

Next, we will see the Java implementation of the Insertion sort technique.

Java Example

public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Input list of elements ..."); for(int i=0;i<10;i++) { System.out.print(myarray[i] + " "); } for(int k=1; k<10; k++) { int temp = myarray[k]; int j= k-1; while(j>=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println("\nsorted list of elements ..."); for(int i=0;i<10;i++) { System.out.print(myarray[i] + " "); } } }

Output:

Inputlistofelements

12 4 3 1 15 45 33 21 10 2

sortedlistofelements

1 2 3 4 10 12 15 21 33 45

In both the implementations, we can see that we begin sorting from the 2nd element of the array (loop variable j = 1) and repeatedly compare the current element to all its previous elements and then sort the element to place it in its correct position if the current element is not in order with all its previous elements.

Insertion sort works the best and can be completed in fewer passes if the array is partially sorted. But as the list grows bigger, its performance decreases. Another advantage of Insertion sort is that it is a Stable sort which means it maintains the order of equal elements in the list.

Complexity Analysis Of The Insertion Sort Algorithm

From the pseudo code and the illustration above, insertion sort is the efficient algorithm when compared to bubble sort or selection sort. Instead of using for loop and present conditions, it uses a while loop that does not perform any more extra steps when the array is sorted.

However, even if we pass the sorted array to the Insertion sort technique, it will still execute the outer for loop thereby requiring n number of steps to sort an already sorted array. This makes the best time complexity of insertion sort a linear function of N where N is the number of elements in the array.

Thus the various complexities for Insertion sort technique are given below:

In spite of these complexities, we can still conclude that Insertion sort is the most efficient algorithm when compared with the other sorting techniques like Bubble sort and Selection sort.

Conclusion

Insertion sort is the most efficient of all the three techniques discussed so far. Here, we assume that the first element is sorted and then repeatedly compare every element to all its previous elements and then place the current element in its correct position in the array.

In this tutorial, while discussing Insertion sort we have noticed that we compare the elements using an increment of 1 and also they are contiguous. This feature results in requiring more passes to get the sorted list.

In our upcoming tutorial, we will discuss Shell sort which is an improvement over the Selection sort.

In shell sort, we introduce a variable known as increment or a gap using which we divide the list into sublists containing non-contiguous elements that gap apart. Shell sort requires fewer passes when compared to Insertion sort and is also faster.

In our future tutorials, we will learn about two sorting techniques, Quicksort and Mergesort which use Divide and conquer strategy for sorting data lists.

=> Watch Out The Beginners C++ Training Guide Here.