Insertion Sort Algorithm in C

Insertion Sort Algorithm in C

8 mins read1.3K Views Comment
Updated on Jan 2, 2024 13:44 IST

Insertion sort in C is an algorithm that efficiently organizes a list by sequentially inserting each element into its proper place within a partially sorted section. This technique, akin to sorting hand-held cards, excels in simplicity and efficiency, especially for smaller arrays, making it a fundamental algorithm in C programming.

 

Insertion sort in C is a straightforward, efficient sorting algorithm, particularly useful for small datasets. It works by building a sorted array one element at a time, picking each element from the unsorted section and inserting it into its correct position in the sorted part. This method mimics the way you might sort playing cards in your hands, making it intuitive and easy to implement in C programming. Let's understand.

Explore: C Programming Courses and Certifications

Table of Content

How Does Insertion Sort Work?

Insertion Sort is the embodiment of precision—meticulous and straightforward. It's akin to organizing a hand of playing cards. Here's how it unfolds:

  1. Pick Up: Starting from the second element, consider it separate from the sorted portion of the array.
  2. Compare and Place: Move back through the array, comparing this element with each preceding one.
  3. Insert: Once the correct position is found where this element is greater than (or equal to) the left element and less than the right one, insert it there.

Implementing Arrays in C Programming
Implementing Arrays in C Programming
In C programming, arrays are used to store multiple values of the same type in a single variable. To implement an array, you define its type and size, then initialize...read more

C Strings with Examples
C Strings with Examples
C strings is a very important topic.This topic covers topics like assigning values to C string,reading C strings,passing c string to a function.

This process repeats for each element until the entire array is sorted.

Illustration:

Here’s a relatable way to picture Insertion Sort:

  • Imagine you're sorting a toolset. You have a series of slots, and you start with the second tool.
  • You compare this tool with the one in the previous slot and swap if necessary.
  • Continue comparing backwards until you find the correct slot for this tool where it fits just right.

This cycle continues until each tool is neatly sorted in its place.

Insertion Sort is an algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but has the advantage of being simple to understand and can perform well on small lists or lists that are mostly sorted.

Algorithm

Step 1: Start with the second element: Consider the first element as already sorted.

Step 2: Iterate through the remaining elements:

  • Pick the current element.
  • Compare it with the element to its left.
  • If the current element is smaller, swap them.
  • Continue comparing and swapping with elements to the left until the correct position is found.

Step 3: Repeat for each element: Continue this process for all elements in the array.

Let's walk through the Insertion Sort steps, explaining the process as if we are sorting cards in our hands:

Initial Array (Step 0):

We start with the array [5, 10, 2, 9, 3]. This will be our unsorted list of cards that we hold in our hand, face up, but out of order.

Step 1:

We start at the second element of the array, which is 10. Since 10 is greater than 5, it is already in the correct position relative to the first element. We leave it as it is.

Step 2:

Next, we move to the third element, 2. We compare 2 to the elements before it and insert it into the correct position. Here, 2 is less than 10, so we swap 2 with 10. Now, 2 is also less than 5, so we continue to swap it leftwards until it's in the correct position. The array now looks like [2, 5, 10, 9, 3].

 

Step 3:

We proceed to the fourth element, 9. We compare 9 to the elements before it and start swapping it leftwards until it's in the right position. 9 is less than 10, so we swap them. 9 is greater than 5, so 9 is now in the correct position. The array is now [2, 5, 9, 10, 3].

 

Step 4:

Finally, we move to the last element, 3. We compare 3 to the elements before it and insert it into the correct position. 3 is less than 10 and 9 but greater than 2, so we place 3 between 2 and 5. The array is now [2, 3, 5, 9, 10].

The array is now fully sorted. At each step, we took the next card (element) and moved it past any cards higher in value, inserting it into its correct sorted position. This process is repeated until all the cards (elements) are sorted correctly in our hand (the array).

 

Dry Run

Pass

Iteration

Array

1

1

[5, 10, 2, 9, 3]

2

1

[5, 2, 10, 9, 3]

2

2

[2, 5, 10, 9, 3]

3

1

[2, 5, 9, 10, 3]

4

1

[2, 5, 9, 3, 10]

4

2

[2, 5, 3, 9, 10]

4

3

[2, 3, 5, 9, 10]

The process of Insertion Sort is similar to how one might organize a hand of playing cards, picking cards one by one and inserting them into their correct position. It's a straightforward algorithm that can be efficient for small datasets or datasets that are already mostly sorted.

Pseudo Code:

Before we roll up our sleeves and dive into C code, let’s draft a blueprint with pseudo-code:

function insertionSort(array)

    for index from 1 to length(array)

        key = array[index]

        j = index - 1

        while j >= 0 and array[j] > key

            array[j + 1] = array[j]

            j = j - 1

        array[j + 1] = key

Code (C) with proper comments:


 
// Function to perform insertion sort
void insertionSort(int arr[], int n) {
int i, key, j;
// Loop from the second element of the array
for (i = 1; i < n; i++) {
key = arr[i]; // The element to be inserted
j = i - 1;
/* Move elements of arr[0..i-1], that are greater than key,
to one position ahead of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // Insert the key at the correct position
}
}
Copy code

Time Complexity

The time complexity of an algorithm is a measure of how long it will run to the size of the input. For Insertion Sort, it varies:

  • Best Case (Already Sorted): Runs in O(n) time, as each element needs only to be compared with its predecessor.
  • Worst Case (Reversely Sorted): Needs O(n^2) comparisons and swaps since each element is compared with all other elements in the sorted array.
  • Average Case: Generally requires O(n^2) time, but performs well with nearly-sorted arrays.

Space Complexity

Insertion Sort is an in-place sorting algorithm, meaning it doesn't require additional storage. Thus, its space complexity is:

  • In-Place Storage: O(1) - It only requires a small, constant amount of additional space.

Quick Sort in C
Quick Sort in C
Have you ever wondered how large datasets are sorted efficiently in programming? Quick Sort in C is the answer, utilizing a divide-and-conquer strategy to sort arrays rapidly by partitioning them...read more

Merge Sort Algorithm (With Code)
Merge Sort Algorithm (With Code)
Merge Sort Algorithm is one of the sorting algorithm similar to selection sort, insertion sort, quick sort algorithms. In this article, we will briefly discuss merge sort algorithm and its...read more

Real-World Example

Let's consider a real-world example where you have a hand of cards in a card game that are unordered and you want to sort them using the Insertion Sort algorithm. The task is to arrange the cards in your hand in ascending order based on their values.

Task:

Sort a hand of playing cards in ascending order using the Insertion Sort algorithm.

Solution Approach:

  • Consider a hand of playing cards where each card has a value associated with it (e.g., Ace, 2, 3, ..., King).
  • Use the Insertion Sort algorithm to sort the cards in your hand based on their numerical value.
  • Iterate through the unsorted part of the hand, picking one card at a time and inserting it into its correct position in the sorted part of the hand.

Code in C:


 
#include <stdio.h>
// Function to perform Insertion Sort on an array of cards
void insertionSort(int cards[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = cards[i];
j = i - 1;
// Move elements of cards[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && cards[j] > key) {
cards[j + 1] = cards[j];
j = j - 1;
}
cards[j + 1] = key;
}
}
int main() {
int hand[] = {5, 10, 2, 9, 3}; // Example hand of cards (values represented as integers)
int handSize = sizeof(hand) / sizeof(hand[0]);
printf("Unsorted hand of cards: ");
for (int i = 0; i < handSize; i++) {
printf("%d ", hand[i]);
}
printf("\n");
insertionSort(hand, handSize);
printf("Sorted hand of cards: ");
for (int i = 0; i < handSize; i++) {
printf("%d ", hand[i]);
}
printf("\n");
return 0;
}
Copy code

Output:

Unsorted hand of cards: 5 10 2 9 3

Sorted hand of cards: 2 3 5 9 10

Shell Sort: Advantages and Disadvantages
Shell Sort: Advantages and Disadvantages
Shell Sort was introduced by Donald Shell in 1959 and is known for its efficiency compared to other sorting algorithms. It is a variation of insertion sort that provides better...read more

Selection Sort Algorithm in C
Selection Sort Algorithm in C
Ever wondered how your favorite music app arranges songs from least to most played, or how an online store lists products from cheapest to priciest? At the heart of such...read more

Advantages of Insertion Sort:

  • Simple: It's one of the easiest sorting algorithms to understand and implement.
  • Efficient for small datasets: It performs well for small or partially sorted arrays.
  • In-place: It doesn't require additional memory space, as it sorts elements within the original array.
  • Stable: It preserves the relative order of elements with equal keys.
  • Online: It can sort elements as they are received, making it suitable for real-time applications.

Bubble Sort Algorithm (With Code)
Bubble Sort Algorithm (With Code)
In today’s world of continuous data generation, it is of utmost importance for all businesses to sort data linearly and attain relationships on the same. With different types...read more

Introduction to Quicksort Algorithm
Introduction to Quicksort Algorithm
Sorting is organizing the data in a systematic manner, in data structures we have various kinds of sorting algorithms. Quick sort is one of the widely implemented, quick, and efficient...read more

Disadvantages of Insertion Sort

  • Less efficient for large datasets: Its time complexity of O(n^2) makes it less efficient for larger datasets compared to algorithms like Quick Sort or Merge Sort (which have O(n log n) complexity).
  • Not adaptivein: It doesn't take advantage of partially sorted arrays, unlike algorithms like Timsort or Insertion Sort with binary search.

Contributed By: Manali Bhave

Top FAQs on Insertion Sort in C

Is Insertion Sort suitable for large datasets?

Insertion Sort is typically not the best choice for large datasets as its average and worst-case time complexity is O(n^2). However, for small datasets, it's quite efficient.

How does Insertion Sort handle duplicate values?

Insertion Sort is a stable sorting algorithm, so it maintains the relative order of records with equal keys (i.e., duplicate values).

Why use Insertion Sort when other algorithms have better time complexity?

Despite having a higher time complexity, Insertion Sort has a lower overhead and is faster than more complex algorithms like Quick Sort and Merge Sort for small datasets. It's also easy to implement and requires no additional memory, which can be a significant advantage in certain situations.

Can Insertion Sort be used for linked lists?

Yes, Insertion Sort can be particularly efficient for linked lists because elements can be inserted with minimal movement, unlike in arrays where shifting is costly.

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio