you are here->home->Class 12->Insertion Sort
Insertion Sort

# Objective

To implement a program to sort a list of elements using the insertion sort algorithm.

# Theory

Insertion sort is a simple sorting algorithm that works like the sorting of playing cards in hands.

Imagine you have a deck of cards in your hand, and you want to arrange them in ascending order. Here's how Insertion Sort works:

• Start with the first card: Consider the first card in your hand as the "sorted" part.
• Pick the next card: Take the next card and compare it with the cards in the "sorted" part.
• Insert into the correct position: Insert the card into the correct position in the "sorted" part by shifting the larger cards to the right.
• Repeat: Repeat steps 2-3 for each remaining card until the entire deck is sorted.

Similarly, insertion sorting works by dividing a list into two parts: a sorted sub-list and an unsorted sub-list. Initially, the sorted sub-list contains only the first element of the list, and the unsorted sub-list contains the rest of the elements.

The algorithm iterates through the unsorted sub-list, taking one element at a time, and inserts it into its correct position in the sorted sub-list. To insert an element, the algorithm compares it with the elements in the sorted sub-list from right to left until it finds the correct position for the element.

The insertion sort algorithm has a time complexity of O(n^2) in the worst case and O(n) in the best case when the input list is already sorted.

Insertion sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the sorted list. It is also an in-place sorting algorithm, meaning that it does not require any additional memory for sorting.

Insertion sort is useful for sorting small to medium-sized lists or partially sorted lists. However, it is not efficient for sorting large lists due to its quadratic time complexity.

E.g. Initial list: [5, 2, 9, 1, 5]

Pass 1:

• Sorted: [5], Element to Insert: 2
• Compare 2 with 5 (shift 5 to the right).
• Insert 2 at the correct position.
• Result: [2, 5, 9, 1, 5]

Pass 2:

• Sorted: [2, 5], Element to Insert: 9
• Compare 9 with 5 (no shift needed).
• Insert 9 at the correct position.
• Result: [2, 5, 9, 1, 5]

Pass 3:

• Sorted: [2, 5, 9], Element to Insert: 1
• Compare 1 with 9 (shift 9 to the right).
• Compare 1 with 5 (shift 5 to the right).
• Compare 1 with 2 (shift 2 to the right).
• Insert 1 at the correct position.

Result: [1, 2, 5, 9, 5]

Pass 4

• Sorted: [1, 2, 5, 9], Element to Insert: 5
• Compare 5 with 9 (shift 9 to the right).
• Compare 5 with 5 (shift 5 to the right).
• Insert 5 at the correct position.

Result: [1, 2, 5, 5, 9]

The final sorted list is  [1, 2, 5, 5, 9]. This process of picking, comparing, and inserting continues until all elements are in their correct order.

# Learning Outcomes

• Understanding of sorting algorithms: Implementing the insertion sort algorithm requires an understanding of sorting algorithms, their time complexity, and their advantages and disadvantages.
• Familiarity with list manipulation: The insertion sort algorithm involves manipulating lists by shifting elements to make room for a new element to be inserted in its correct position. Implementing the insertion sort algorithm requires familiarity with lists manipulation techniques.
• Ability to implement algorithms: Implementing the insertion sort algorithm requires programming skills such as using loops, conditionals, and lists operations to perform the necessary computations.
• Ability to analyze algorithms: Analyzing the time complexity of the insertion sort algorithm can help students gain an understanding of algorithmic efficiency and the trade-offs between time and space complexity.
• Problem-solving skills: Implementing the insertion sort algorithm requires problem-solving skills to identify the inputs needed, the steps involved in the algorithm, and the output to be generated.