- Introduction to Challenges
- Insertion Sort 1
- Insertion Sort Itself
- Correctness and the Loop Invariant
- Running Time
Counting Sort 1
- Simple Counting Sort
- Prepare for Full Counting Sort
- The Full Counting Sort
- Simple Quick Sort
- Quick-Sort Advanced
- Quick Sort Running Time
Input Format for standard Sorting Challenges:
- t - the number of test cases
- s - the size of the array
- ar - the list of integers
Insertion Sort 1
Goal: Before sorting entire lists, sort one element in a list.
Given a sorted list of numbers with an unsorted number V in the right-most spot, can you write some simple code to insert V into the list so it remains sorted?
Print the list every time a value is shifted, until the list is fully sorted. The goal of this challenge is to follow the correct order of insertion sort.
How to Solve: Use the standard boilerplate to process the numbers into an array. You can then copy the right-most value (V) to a variable, and consider its cell “empty”. Since this leaves an extra cell empty on the right, you can shift every number over until V can be inserted. This will create a duplicate of each value, but when you reach the right spot, you can replace a value with V.
Output Format On each line, output the entire array every time an item is shifted in it. This will include duplicate values.