Howto: Code the Insertion Sort in the C Language + Insertion Sort Tutorial

Howto: Code the Insertion Sort in the C Language + Insertion Sort Tutorial

The insertion sort is a simple algorithm which can sort an unsorted array of numbers into a sorted array.

Insertion sort has a performance complexity of O(n2)

The algorithm works by by assuming the first node in a given array is already sorted as a sublist of one. It then looks at the following nodes, and Inserts them in the correct spot in the preceeding sorted sub-list. This sorted sub-list continues to grow until eventually all nodes are sorted.

Here is a quick step by step tutorial on how the insertion sort works in practice.

Step 1
For example, if our initial unsorted numbers were as follows:

10, 24, 3, 65, 54, 33, 94, 87, 47, 79

We first assume the first number 10, is already sorted in a list by itself.

We then start with the second number, 24, and place it in the correct order with respect to the 10. It in this case, it is already sorted.

10, 24, 3, 65, 54, 33, 94, 87, 47, 79

Step 2
We then take the third number, and again now knowing that the first two numbers are sorted, we can now Insert the third number in the correct spot. In this case we check both the 24 and the 10, and find that it should be inserted into the first spot. This is done by sliding the two numbers 10 and 24 up one spot, and then inserting the number 3 in the first spot.

3, 10, 24, 65, 54, 33, 94, 87, 47, 79

Step 3
Now that the first three numbers are sorted, we move on to the fourth number the 65. Again we look to find where it should be inserted, and see it should stay in place.

3, 10, 24, 65, 54, 33, 94, 87, 47, 79

Step 4

Next we look at the fifth number 54, insert it into the corect spot, by sliding the 65 back one spot and inserting it in the existing spot where the 65 was.

3, 10, 24, 54, 65, 33, 94, 87, 47, 79

Step 5 - 8

And on and on we go all the way through the last number 79.

...repeat algorithm...

Step 9

The final step is sorting the last node in the array, the 79.

3, 10, 24, 33, 47, 54, 65, 87, 94, 79

We use our usual Insert method, and slide the 87 and 94 up one spot, and place it in the correct spot between the 65 and 87.

Here is our final sorted sorted list:

3 10 24 33 47 54 65 79 87 94

We can implement this in C code by placing the following code in a file called insertion-sort.c

#include <stdio.h>

int main() {

    // Declare variables
    int i, j, cnt = 10, tmp; 

    // Initialize unsorted array
    int arr[10] = { 10, 24, 3, 65, 54, 33, 94, 87, 47, 79 };

    // Print unsorted array
    printf("Unsorted: ");
    for (i = 0; i < cnt; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");

    // Perform insertion sort
    for (int i = 1; i < cnt; i++) {
        tmp = arr[i];
        j = i - 1;
        while(tmp < arr[j] && j >= 0) {
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = tmp;
    }

    // Print sorted array
    printf("  Sorted: ");
    for (i = 0; i < cnt; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");

    // Exit without error
    return 0;
}

We can then compile the code with the following command:

$ gcc insertion-sort.c

And finally we can run it with the following command:

$ ./a.out
Unsorted: 10 24 3 65 54 33 94 87 47 79 
  Sorted: 3 10 24 33 47 54 65 79 87 94

Congratulations, you have succesfully implemented an Insertion Sort in the C language.


Share Tweet Send
0 Comments
Loading...
You've successfully subscribed to Linux Developer
Great! Next, complete checkout for full access to Linux Developer
Welcome back! You've successfully signed in
Success! Your account is fully activated, you now have access to all content.