A12 — Sorting algorithms
Investigate sorting algorithms.
Due Nov 18, 2026
Estimated time to complete (just the assignment, excluding the prep materials): 60–90 minutes.
Prep materials: Week 12: Algorithms continued
What to do
Submit all your answers to Assignment 12 Submission on Brightspace. You can use a text response field, a text file, or a Markdown file.
Imagine you need to sort a sequence of numbers, and you are given a choice of two sorting algorithms: insertion sort and selection sort. In the prep materials, you have already worked with those algorithms, and you might or might not remember exactly how they work. Do not try to go back and look at the prep materials until step 3.
Search the Internet/AI for information about how insertion sort and selection sort compare. In the text response, include the query/prompt that you used and copy and paste the relevant information you found, with references.
Does the information you found mention:
- The complexity of the algorithms in the average case?
- The complexity of the algorithms in the best case?
- Any particular considerations when choosing between them?
If not, refine your prompt until you find that information, and include the prompt and the information you found in your response.
Using your own example of a sequence of 4 numbers that is not sorted (and also not sorted in reverse order), show each step of sorting the sequence with both algorithms.
You can use the example below as a template, but you need to use your own sequence of 4 numbers.
- For selection sort, the write-up needs to talk about comparisons and swaps.
- For insertion sort, the write-up needs to talk about comparisons, insertions, and numbers shifted.
If you aren’t sure how each algorithm works, now is the time to review.
Using your own example of a sequence of 4 numbers that is already sorted, show each step of sorting the sequence with both algorithms.
Looking at the information you found earlier, do the examples you worked through seem consistent with the findings about the complexity and particular considerations?
- If yes, how?
- If not, why not?
Did the exercise help you better understand the information you found earlier?
- If yes, give one example of a claim that has become clearer to you.
- If there is any part of the information that is unclear, what is it? (You don’t need to try to understand this further now unless you want to.)
Example write-up
Insertion sort for the sequence [3, 1, 2]:
Step 1: take 1 and insert it in the right place
- compare 1 vs 3, 1 is smaller, no more elements to compare
- insert 1 before 3, shifting 3 to the right
[1, 3, 2]
Step 2: take 2 and insert it in the right place
- compare 2 vs 3, 2 is smaller
- compare 2 vs 1, 2 is larger
- insert 2 between 1 and 3, shifting 3 to the right
[1, 2, 3]
Total: 3 comparisons, 2 insertions, 2 numbers shifted
Grading
Graded for completion.