Insertion Sort in MATLAB | MATLAB Tutorial

Insertion Sort in MATLAB |  MATLAB Tutorial
  • It is a simple Sorting algorithm which sorts the array by shifting elements one by one.
  • This is an in-place sorting algorithm.  An element which is to be ‘insert’ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

 

Pseudo Code:

 

INSERTION-SORT (A)

1 for j <- 2 to length [A]

2 do key <- A[j]

3 Insert A[j] into the sorted sequence A[1 . . j – 1].

4 i <- j – 1

5 while i > 0 and A[i] > key

6 do A[i + 1] <- A[i]

7 i <- i – 1

8 A[i + 1] <- key

 

Explanation of Insertion Sort Using an Example:

out = [5, 1, 6, 2, 4, 3];
for i = (2:numel(out))

    key = out(i);
    j = i - 1;
    while (j >= 1) & (out(j) > key)
        out(j+1) = out(j);
        j = j-1;
    end

    out(j+1) = key;

end
out

  • Now let’s, understand the above simple insertion sort algorithm. We took an array with 5 integers. We took a variable key, in which we put each element of the array, in each pass, starting from the second element, that is out[2].
  • Then using the while loop, we iterate, until j becomes equal to 1 or we find an element which is greater than key, and then we insert the key at that position.
  • In the above array, first we pick 1 as key, we compare it with 5(element before 1), 1 is smaller than 5, we shift 1 before 5. Then we pick 6, and compare it with 5 and 1, no shifting this time. Then 2 becomes the key and is compared with, 6 and 5, and then 2 is placed after 1. And this goes on, until complete array gets sorted.

 

MATLAB CODE:

%function for insertion sort
function out = insertionSort(out)

for i = (2:numel(out))

    val = out(i);
    j = i - 1;
    while (j >= 1) && (out(j) > val)
        out(j+1) = out(j);
        j = j-1;
    end

    out(j+1) = val;

end
end

Time Complexity Analysis:

i=1;
k = 1:100:10000;
val = zeros(1,length(j));
for j = 1:100:10000   %array size

    R = randn([1 j]); %generating array of size j containing random elements
    tic;              %starting the timer
    P = insertionSort(R);%calling the insertion sort function
    val(i) =toc; %stopping the timer and creating an array of time difference

    i=i+1;

end

plot(k,val); %plotting array size vs time taken for sorting using insertion sort algorithm
grid on;
xlabel('array length');
ylabel('Time Taken in seconds');
title('Analysis Plot');
legend('Insertion Sort')

 

Simulation Results:

 

 

Explanation:

  • As we can see from the above plot that as the size of the array increases the time taken to perform insertion sorting on the data increases. And thus for the data of very large size the time taken would be quite large which is not feasible and thus would create problems.
  • Now we can know the time complexity of the algorithm by performing the curve fitting and then analysing the equation of the curve as shown below:

 

 

As shown in the figure, linear plotting does not fit to the curve but the quadratic equation passes through our generated output. The time complexity is decided by the largest power of the variable x. Thus the time complexity can be said to be O(n2).

 

Time Complexity:-

  • Worst Case Time Complexity: O(n2)
  • Best Case Time Complexity: O(n)
  • Average Time Complexity: O(n2)
  • Space Complexity: O(1)

 

 


Experienced Programmer skilled in Machine Learning, MATLAB, Java, MySQL, and MongoDB. Strong engineering professional persuing a Bachelor’s Degree focused in Information and Communication Technology from School of Engineering & Applied Sciences, Ahmedabad University.