Insertion Sort Algorithm in C
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?
- Time Complexity
- Space Complexity
- Advantages of Insertion Sort
- Disadvantages of Insertion Sort
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:
- Pick Up: Starting from the second element, consider it separate from the sorted portion of the array.
- Compare and Place: Move back through the array, comparing this element with each preceding one.
- 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.
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 sortvoid 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 }}
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
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.
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 cardsvoid 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;}
Output:
Unsorted hand of cards: 5 10 2 9 3
Sorted hand of cards: 2 3 5 9 10
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.
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.
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
Top Picks & New Arrivals
