Insertion Sort Algorithm Worksheet
A Grade 12 math worksheet on the Insertion Sort Algorithm, covering its mechanics, steps, and analysis.
Includes
Topics
Insertion Sort Algorithm
Name:
Date:
Score:
Read each question carefully and provide your answers in the space provided. Show all your work for full credit.
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
1. Simple implementation. 2. Efficient for (and works fast on) small data sets. 3. Efficient for data sets that are already substantially sorted. 4. Stable; i.e., does not change the relative order of elements with equal keys. 5. In-place; i.e., only requires a constant amount O(1) of additional memory space.
1. Briefly explain the main idea behind the Insertion Sort algorithm.
2. List two advantages of using Insertion Sort.
1. Insertion sort builds the final sorted array one at a time.
2. For large datasets, Insertion Sort is generally less efficient than algorithms like sort or sort.
Apply the Insertion Sort algorithm to sort the following array in ascending order. Show each step of the process clearly.
[8, 2, 4, 9, 3, 6]
1. What is the time complexity of Insertion Sort in the worst-case scenario?
O(n)
O(n log n)
O(n^2)
O(log n)
2. When is Insertion Sort most efficient?
When the array is randomly ordered
When the array is nearly sorted
When the array contains duplicate elements
When the array is sorted in descending order
1. Insertion Sort is an unstable sorting algorithm.
True
False
2. Insertion Sort requires O(1) additional memory space.
True
False
1. Describe a scenario where Insertion Sort would be a preferred sorting algorithm over more complex ones like Quick Sort.