Insertion Sort Algorithm

Introduction to Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Insertion sort is more suitable for small data sets or nearly sorted data sets because of its simplicity and efficiency in those cases.

---

Step-by-Step Process

Consider an array with the following elements:

[12, 11, 13, 5, 6]

To sort this array using insertion sort, follow these steps:

1. Start with the Second Element: Assume the first element is sorted. Take the second element and compare it with the elements in the sorted part of the array.
2. Compare and Shift: If the second element is smaller than the first, shift the first element to the right and insert the second element at the beginning.
3. Continue to Next Elements: Take the next element and compare it with the elements in the sorted part of the array. Shift the larger elements to the right and insert the current element at the correct position.
4. Repeat: Continue this process until all elements are sorted.

Let's apply these steps to the example array:

• Initial array: [12, 11, 13, 5, 6]
• Step 1: Insert 11 in the sorted part [12] -> [11, 12, 13, 5, 6]
• Step 2: Insert 13 in the sorted part [11, 12] -> [11, 12, 13, 5, 6]
• Step 3: Insert 5 in the sorted part [11, 12, 13] -> [5, 11, 12, 13, 6]
• Step 4: Insert 6 in the sorted part [5, 11, 12, 13] -> [5, 6, 11, 12, 13]

---

Pseudo Code for Insertion Sort

Below is the pseudo code for the insertion sort algorithm:

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

Explanation:

• Initialize: The function starts by iterating through the array from the second element to the last element.
• Compare and Shift: For each element, the key is compared with the elements in the sorted part of the array. If the key is smaller, the elements are shifted to the right.
• Insert: The key is inserted at the correct position in the sorted part of the array.
• Repeat: The process repeats until the entire array is sorted.

---

Python Program to Implement 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
    return arr

# Example usage:
array = [12, 11, 13, 5, 6]
print("Original array:", array)
sorted_array = insertion_sort(array)
print("Sorted array:", sorted_array)  # Output: [5, 6, 11, 12, 13]

This Python program defines a function to perform insertion sort on an array. The function iterates through the array, compares the current element with the sorted elements, shifts the larger elements to the right, and inserts the current element at the correct position.