Understanding Sorting and Searching: Insertion Sort and Linear Search

In the world of computer science, sorting and searching are two fundamental operations that underpin many complex algorithms and data structures. In this article, we’ll explore two straightforward algorithms — Insertion Sort for sorting, and Linear Search for searching — with a step-by-step breakdown, pseudocode, and Python code.

Insertion Sort: Sorting with Simplicity

Insertion Sort is a simple sorting algorithm, akin to the way we arrange playing cards in our hands. It iterates through the array and, for each element, finds its correct position within the already sorted section of the array.

Pseudocode for Insertion Sort

Insertion-Sort(A)
1. for i = 2 to length[A]
2.     key = A[i]
3.     j = i - 1
4.     while j > 0 and A[j] > key
5.         A[j + 1] = A[j]
6.         j = j - 1
7.     A[j + 1] = key

Python Code for Insertion Sort

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key