Sorting CS Thinking Example 3
Follow the full solution, then compare it with the other examples linked below.
Example 3
mediumSort [4, 1, 3] using insertion sort. Show each step.
Solution
- 1 Step 1: Start with [4]. Insert 1: 1 < 4, so [1, 4]. Insert 3: 3 < 4 but 3 > 1, so [1, 3, 4].
- 2 Step 2: Final sorted list: [1, 3, 4]. Two insertions were needed.
Answer
[1, 3, 4]
Insertion sort builds the sorted list one element at a time, inserting each new element into its correct position. It is efficient for small or nearly-sorted lists.
About Sorting
Rearranging items in a collection into a defined order, such as smallest to largest or alphabetical. Sorting is one of the most studied problems in computer science, with algorithms ranging from simple (bubble sort, ) to efficient (merge sort, ).
Learn more about Sorting →More Sorting Examples
Example 1 medium
Sort the list [5, 2, 8, 1, 9] using bubble sort. Show the first two passes.
Example 2 hardCompare bubble sort and merge sort in terms of time complexity. When would you choose one over the o
Example 4 mediumYou have a list of exam scores that is already sorted except one new score was added at the end. Wou