Welcome back, data enthusiasts! 💻📊 In our first post, we explored the world of Bubble sort, Selection sort, and Quick sort, but the sorting journey doesn't end there. In this post, we'll dive even deeper into the world of data organisation and learn about Insertion sort, Merge sort, and Heap sort. Get ready to master these powerful techniques and take your data sorting skills to the next level! 🔜

Insertion Sort: From the Short & Sweet to the King of Efficiency 🚀

Hi, it's Kunal and Priyansh, the dynamic duo behind this series on sorting algorithms. In our first post, we talked about the bubbly Bubble Sort and the selective Selection Sort. And today, we're going to introduce you to one of the simplest, yet most efficient, sorting algorithms: the Insertion Sort 💡

Insertion sort is a simple sorting 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 when it comes to small or partially sorted arrays, it's the king of the game 🔝

To understand how it works, let's imagine that we have a deck of cards. We want to sort the deck in ascending order, so we start by picking up the first card, which becomes our sorted portion of the deck. Then, we pick up the next card, compare it with the cards already in our sorted portion, and insert it in its correct position. We repeat this process until we have sorted all the cards 🃏

This is exactly how the insertion sort algorithm works. The algorithm divides the input into two parts: the sorted portion and the unsorted portion. It iterates through the unsorted portion, picks an element and inserts it in its correct position in the sorted portion. It does this by swapping elements until it finds the right spot for the picked element.

Time Complexity:

The time complexity of Insertion Sort depends on the size of the input array. In the best-case scenario, the array is already sorted and it takes O(n) time, where n is the number of elements in the array. But in the worst-case scenario, the array is sorted in descending order, and it takes O(n^2) time.

Space Complexity:

The space complexity of Insertion Sort is O(1), which means it requires a constant amount of memory to sort the elements. It performs the sorting in-place, meaning it sorts the elements within the same array and doesn't require any additional memory.

Use Cases:

Insertion sort is a simple sorting algorithm that is easy to understand and implement. It's an efficient sorting algorithm for small arrays and partially sorted arrays. It's also used as a subroutine in other sorting algorithms such as Shell Sort.

Here's an example of sorting an array of numbers in ascending order using the Insertion Sort algorithm in C++:

#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
   int i, key, j;
   for (i = 1; i < n; i++) {
      key = arr[i];
      j = i - 1;
      while (j >= 0 && arr[j] > key) {
         arr[j + 1] = arr[j];
         j = j - 1;
      }
      arr[j + 1] = key;
   }
}
void printArray(int arr[], int n) {
   int i;
   for (i = 0; i < n; i++)
      cout << arr[i] << " ";
   cout << endl;
}
int main() {
   int arr[] = { 12, 11, 13, 5, 6 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Array before sorting: \n";
   printArray(arr, n);
   insertionSort(arr, n);
   cout << "Array after sorting: \n";
   printArray(arr, n);
   return 0;
}

The code shown above is an implementation of Insertion Sort in C++. This sorting algorithm is a simple sorting algorithm that works by building the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as QuickSort, MergeSort, or HeapSort, but it has the advantage of being very easy to understand, simple to implement, and highly efficient for small lists or lists that are already partially sorted.

In the code, we first initialise an array of integers and its size. Then, we define the insertionSort function which takes the array and its size as arguments.

The sorting process starts with the second element of the array (index 1) and compares it with the first element (index 0). If the second element is smaller than the first, we swap them. This process continues for each subsequent element in the array until all elements are sorted.

The outer loop of the function iterates over the elements of the array from the second element to the last. The inner loop, starting from the current outer loop index, compares each element with the previous one and if it is smaller, it swaps them. This inner loop continues until the element is in its correct position.

At the end, the sorted array is displayed using a for loop.

It's important to note that Insertion Sort has a time complexity of O(n^2) in the worst case scenario. However, its best case time complexity is O(n) when the list is already sorted or partially sorted. The space complexity of Insertion Sort is O(1), meaning that it requires a constant amount of memory to perform the sorting.

This sorting algorithm is useful for small lists or when the list is already partially sorted. It can also be used as a subroutine in more advanced algorithms to sort smaller sublists.

In conclusion, insertion sort is a simple and efficient sorting algorithm that works well for small arrays or partially sorted arrays. It has a space complexity of O(1), making it an in-place sorting algorithm. The time complexity of insertion sort ranges from O(n) for the best-case scenario to O(n^2) for the worst-case scenario, making it suitable for arrays with a small number of elements. Although insertion sort may not be as fast as some other sorting algorithms, it is easy to understand and implement, making it a great starting point for beginner programmers or a useful tool to keep in your algorithmic toolkit. Whether you're just starting out or a seasoned veteran, mastering insertion sort is a valuable step towards becoming a more effective problem-solver.