12.1.4. Example of Insertion Sort

Try these first

1. 1.

   What is the first step in the Insertion Sort algorithm?

   Hint

   Consider one element to be sorted.

2. 2.

   How does the Insertion Sort decide where to place the next unsorted element?

   Hint

   Think about comparing numbers.

3. 3.

   What is the primary concept behind Insertion Sort?

   • Sorts by repeatedly comparing all elements
   • Builds a sorted list incrementally
   • Only works on numeric arrays

   Hint

   Think about how it processes each element.

4. 4.

   Insertion Sort has a time complexity of?

   • True
   • False

   Hint

   Consider the complexity classes.

5. 5.

   Design and implement a function in your preferred programming language to perform Insertion Sort. Test it with different arrays, including sorted, reversed, and unsorted.

   Hint

   Remember to consider the index while comparing elements!

6. 6.

   Optimize the Insertion Sort algorithm by incorporating binary search to find the correct position for each element. Discuss how this affects the overall performance.

   Hint

   Think about the trade-offs between search time and shifting elements.