Insertion Sort Algorithm

Insertion Sort is a simple and efficient comparison-based sorting algorithm suited for small data sets or nearly sorted data. It works similarly to how you might sort playing cards in your hands: one card at a time, by placing each card in its correct position relative to the cards that have already been sorted.

How Insertion Sort Works:

1. Initial Setup:
   • The algorithm divides the list into two parts: a sorted sublist on the left and an unsorted sublist on the right. Initially, the sorted sublist contains only the first element, and the rest of the elements are in the unsorted sublist.
2. Iterative Process:
   • The algorithm iterates over the unsorted sublist, taking one element at a time and inserting it into the correct position within the sorted sublist.
3. Insertion:
   • For each element in the unsorted sublist, the algorithm compares it with the elements in the sorted sublist, starting from the rightmost element.
   • The comparisons continue until the algorithm finds the correct position where the current element is less than or equal to the element on its left and greater than or equal to the element on its right.
4. Shifting Elements:
   • During the insertion process, elements in the sorted sublist are shifted to the right to create space for the current element.
5. Repeat:
   • The process is repeated for all elements in the unsorted sublist until the entire list is sorted.

Characteristics of Insertion Sort:

• Time Complexity:
  • Best Case: O(n) – This occurs when the array is already sorted. In this case, the algorithm only makes n-1 comparisons and no shifts.
  • Average Case: O(n²) – On average, each element is compared with half of the already sorted sublist.
  • Worst Case: O(n²) – This occurs when the array is sorted in reverse order. In this case, the algorithm must compare each element with every other element in the sorted sublist and make numerous shifts.
• Space Complexity:
  • Insertion Sort is an in-place sorting algorithm, meaning it requires only a constant amount O(1) of additional memory space.
• Stability:
  • Insertion Sort is a stable sorting algorithm. Stability refers to the algorithm’s ability to preserve the relative order of records with equal keys (i.e., values).
• Usage:
  • Insertion Sort is particularly useful for small datasets or for sorting lists that are already nearly sorted. It is often used as a building block within more complex algorithms for its simplicity and efficiency with small data.

Code Example

def insertionSort(array):
    for i in range(len(array)):
        k = array[i]
        j = i - 1
        while j >= 0 and array[j] > k:
            array[j + 1] = array[j]
            j = j - 1
        array[j + 1] = k


myArray = [4, 7, 1, 9, 3, 5, 2]
insertionSort(myArray)

print("Gradual sorting: ")
print(myArray)

Code Explanation

Function Definition

def insertion_sort(arr):

• The function insertion_sort is defined to take a single list arr as its parameter.

Outer Loop

    for i in range(1, len(arr)):

• The outer loop starts from the second element (index 1) and goes to the last element of the array. The index i represents the current element to be inserted into the sorted subarray.

Key Element

        key = arr[i]

• The variable key holds the value of the current element to be sorted into the correct position within the sorted subarray.

Inner Loop Initialization

        j = i - 1

• The variable j is initialized to the index of the last element of the sorted subarray. This variable will be used to compare and shift elements to create space for the key.

Shifting Elements

        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

• The while loop runs as long as j is greater than or equal to 0 and the key is less than arr[j].
• Inside the loop, elements of the sorted subarray that are greater than the key are shifted one position to the right. This creates space for the key to be inserted at its correct position.
• The j index is decremented to move leftwards through the sorted subarray.

Inserting the Key

        arr[j + 1] = key

• Once the correct position is found (when j is less than 0 or key is greater than or equal to arr[j]), the key is inserted into this position.

Return Statement

    return arr

• The sorted array arr is returned.

Example Usage

arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sorted array is:", sorted_arr)

• An example list arr is sorted using the insertion_sort function, and the sorted list is printed.

Output

Sorted array is: [5, 6, 11, 12, 13]

• The final output is the sorted array in ascending order.