Our Objective

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

The Theory

Insertion sort is a simple sorting algorithm that works by dividing an array into two parts: a sorted sub-array and an unsorted sub-array. Initially, the sorted sub-array contains only the first element of the array, and the unsorted sub-array contains the rest of the elements.

The algorithm iterates through the unsorted sub-array, taking one element at a time, and inserts it into its correct position in the sorted sub-array. To insert an element, the algorithm compares it with the elements in the sorted sub-array 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 array is already sorted. It has a space complexity of O(1) since it does not use any additional memory.

Insertion sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the sorted array. 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 arrays or partially sorted arrays. However, it is not efficient for sorting large arrays due to its quadratic time complexity.

Learning Outcomes 

• Understanding of sorting algorithms: Implementing the insertion sort algorithm requires an understanding of sorting algorithms, their time and space complexities, and their advantages and disadvantages.
• Familiarity with array manipulation: The insertion sort algorithm involves manipulating arrays 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 array manipulation techniques.
• Ability to implement algorithms: Implementing the insertion sort algorithm requires programming skills such as using loops, conditionals, and array 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.