Insertion Sort in MATLAB | MATLAB Tutorial
by Ratnesh Shah
- 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.
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.
- 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.
%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')
- 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).
- Worst Case Time Complexity: O(n2)
- Best Case Time Complexity: O(n)
- Average Time Complexity: O(n2)
- Space Complexity: O(1)