Lecture Notes: Insertion Sort

Introduction to Sorting Algorithms

• Sorting algorithms are essential topics in computer science.
• The unit covers various sorting algorithms, with today's focus on Insertion Sort.

Concept of Insertion Sort

• Objective: Sort a list by partitioning it into a sorted and unsorted section.
• Method: Division of List:
  • Imaginary line separates sorted (left) and unsorted (right) partitions.
  • Initially, the first element is considered to be in the sorted partition.

Procedure of Insertion Sort

• Iteration Process:
  • Move the leftmost element of the unsorted partition to the rightmost position of the sorted partition.
  • If the new element is out of order, shift it to the left until it fits correctly in the sorted partition.
• Repeat until the sorted partition encompasses the whole list.

Example

• Initial Step:
  • Example list: [84, 79, 86, 70]
  • Start with 84 as sorted.
• Subsequent Iterations:
  • Add 79: Swap with 84 since 79 < 84.
  • Add 86: No swap as 86 > 84.
  • Add 70: Move to the leftmost end, as it's the smallest.

Insertion Sort Details

• Imaginary Partitioning:
  • Use colors or marks to visualize sorted and unsorted parts (e.g., green for sorted, gray for unsorted).
  • Move imaginary line rightwards each iteration.
• Best Case:
  • New element is in the correct position, e.g., 5 is already greater than 2.
• Worst Case:
  • Shift element all the way left, e.g., 1 is smallest in list.

Implementation

• Loops Used:
  • Outer Loop: Iterates through indices, moving elements from unsorted to sorted partitions.
  • Inner Loop: Shifts elements left as required.

Performance and Complexity

• Scenarios:
  • Sorted Input: O(n) time complexity as no shifts required.
  • Random Input: Average O(n^2) due to about half elements needing shifting.
  • Reverse Order: Worst case O(n^2) as all elements shift left.

Key Takeaways

• Time Complexity:
  • Best Case: O(n) - Linear
  • Average/Worst Case: O(n^2) - Quadratic
• Efficiency:
  • Performs well with sorted or nearly sorted data.
  • Less efficient with random or reverse-ordered data.