Data Structures and Algorithms

Insertion Sort

A newbie guide to the algorithm and C program which arranges a given set of numbers in ascending order

Is this writer writing an algorithm blog because it ‘sounded cool’ in her head ?

Is she writing one because she just spent half an hour trying to figure out what that word means because she doesn’t understand the crazy stuff written by Jean Paul Tremblay ?

Maybe. You will never know.

Now that this writer has completed ranting, let’s start the blog.

What is algorithm ? — A finite set of instructions that if followed perform a particular task.

What is insertion sorting? — It is an algorithm which basically arranges numbers

Let us see one algorithm which deals with arranging numbers in ascending order.

for j = 2 to length (A)

{

Do key = A [ j ]

i = j — 1

while ( i>0 and A [ i ] > key)

{

do A[ i + 1] = A [ i ]

i =( i -1)

}

A[ i + 1 ] = key

}

Calm down, all these fancy words have no substance, there are all words to do simple tasks.

Let’s take an example.

Arrange in ascending order — 6, 9, 7

Here

6 = A [1]

9 = A [2]

7 = A [3]

So we will start by comparing the second number with the number on its left hand side

Imagine the word ‘key’ to mean an empty box where we can put the number we are comparing.

So right now in the empty box the value ‘9’ is present.

‘ i ‘ will become 2–1 = 1

Now the condition inside the brackets of the while loop will be checked. If both conditions are proved true, then the loop runs. If not it gets skipped to the last line.

Here, i = 1 which is greater than 0 so it’s satisfied. A [ 1 ] = 6 which is lesser than 9 so condition is not satisfied. — (1)

The whole loop gets skipped, and goes back to start.

Now j = 3 gets assigned,

now, key = A [ 3 ] = 7

i = 3–1 = 2

While condition — 2 > 0 and (A [ 2 ] = 9) > 7

Both satisfied so while condition is applied.

A [ 3 ] = A [ 2 ] — so both are assigned value = 9 — (2)

and “i” becomes “i-1” = 2–1 = 1

key remains to be 7.

Now again while loop condition is checked. While condition —

1 > 0 and (A [ 1 ] = 6 ) < 7

condition failed.

so A [ 2 ] = 7 — ( i+1 = 1+1 = 2) is assigned.

now if we have to visualise,

Question — 6 9 7

6 9 7 — because 1st ‘while’ loop — line (1)

6 9 9 — line (2)

6 7 9 — final statement.

Now let’s see the C program of the same!

#include <stdio.h>

int main() {
    
    int key,i,j;
int num[5] = { 8,9,6,3,1};
         printf("%d", num[0]);
         printf("%d", num[1]);
         printf("%d", num[2]);
         printf("%d", num[3]);
         printf("%d \n", num[4]);
 
 for (j = 2; j< 5; j++)
 {
     key = num[j];
     // assigning key = 9 in this example
     i = j-1;
     while (i>=0 && num[i]> key)
     { 
         num[i+1]=num[i];
         i = i-1;}
         
         num[i+1]= key;}
         
         printf("%d", num[0]);
         printf("%d", num[1]);
         printf("%d", num[2]);
         printf("%d", num[3]);
         printf("%d", num[4]);
         return 0;
 }

Output is —

The happiness when <code execution successful> shows up after 5000 trials and errors 😂