17. Insertion Sort
Insertion sort is a simple yet effective algorithm for sorting a list by iteratively building a sorted sequence. The method involves taking one element at a time from the unsorted list and finding its correct position within the sorted section. The process involves comparing and inserting elements into their rightful place, making insertion sort efficient in cases where the list is partially sorted.
Sections
Navigate through the learning materials and practice exercises.
What we have learnt
- Insertion sort constructs a sorted list by repeatedly inserting unsorted elements into their proper position.
- The algorithm shows a best-case performance when the input list is already sorted.
- Insertion sort has a time complexity of O(n^2) in the average and worst cases, but performs better in practice for small or partially sorted datasets.
Key Concepts
- -- Insertion Sort
- An algorithm that sorts a list by picking elements from the unsorted section and inserting them into the sorted section, maintaining the order.
- -- BestCase Performance
- The scenario in which an algorithm performs the least number of operations, in the case of insertion sort, this occurs when the array is already sorted.
- -- Time Complexity
- A computational complexity that describes the amount of time it takes to run an algorithm as a function of the length of the input.
Additional Learning Materials
Supplementary resources to enhance your learning experience.