12.1.3. Iterative Implementation

Try these first

1. 1.

   What is the main concept of Insertion Sort?

   Hint

   Think about arranging cards in your hand.

2. 2.

   What is the time complexity of Insertion Sort?

   Hint

   It's related to how much work is needed as the input grows.

3. 3.

   What is the time complexity of Insertion Sort?

   • O(n)
   • O(n log n)
   • O(n^2)

   Hint

   Think about how many comparisons are needed as the dataset grows.

4. 4.

   True or False: Insertion Sort is ideal for large, randomly ordered datasets.

   • True
   • False

   Hint

   Consider the context of small versus large datasets.

5. 5.

   Given the array [56, 23, 78, 12, 90, 34], manually demonstrate the Insertion Sort method step-by-step.

   Hint

   Remember to find the right spot for each unsorted number.

6. 6.

   Discuss how Insertion Sort would behave if given an already sorted array. What is the time complexity in this case?

   Hint

   Think about the number of swaps needed in a sorted input.