Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm that works by building a sorted sequence one element at a time. It is suitable for small datasets or when the input is partially sorted. However, its time complexity increases rapidly as the size of the dataset grows, making it inefficient for large datasets.

AlgorithmEdit

The Insertion Sort algorithm works as follows:

   Consider the first element of the list as sorted.
   Insert the second element in its correct position in the sorted part of the list.
   Move to the next unsorted element and insert it in its correct position in the sorted part of the list.
   Repeat step 3 until the entire list is sorted.

PseudocodeEdit

Here is a simple pseudocode for Insertion Sort:

function insertionSort(arr)
  for i = 1 to length(arr) - 1
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key
      arr[j + 1] = arr[j]
      j = j - 1
    end while
    arr[j + 1] = key
  end for
end function

Time ComplexityEdit

The worst-case and average time complexity of Insertion Sort is O(n^2), where n is the number of elements in the list. The best-case time complexity is O(n) when the input list is already sorted. In practice, Insertion Sort performs well for small datasets or when the input is partially sorted.

Space ComplexityEdit

The space complexity of Insertion Sort is O(1) because it is an in-place sorting algorithm, meaning it does not require additional memory for temporary storage.

C++ ExampleEdit

Here is an example implementation of Insertion Sort in C++:

#include <iostream>
#include <vector>

void insertionSort(std::vector<int>& arr) {
  size_t n = arr.size();
  for (size_t i = 1; i < n; ++i) {
    int key = arr[i];
    size_t j = i - 1;
    while (j != SIZE_MAX && arr[j] > key) {
      arr[j + 1] = arr[j];
      --j;
    }
    arr[j + 1] = key;
  }
}

int main() {
  std::vector<int> arr = {12, 11, 13, 5, 6};
  insertionSort(arr);

  std::cout << "Sorted array is: ";
  for (int i : arr) {
    std::cout << i << " ";
  }

  return 0;
}