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.