Question

Suppose you have the array of numbers [3 2 5 4 1]. In the style we showed in class, show the contents of the array during a insertion sort.

Answer 1

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by considering one element at a time and inserting it into its correct position within the array.

Step-by-step explanation:

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by considering one element at a time and inserting it into its correct position within the array.

Let's go through the steps of insertion sort for the array [3, 2, 5, 4, 1]:

1. Initially, the first element, 3, is considered sorted.
2. Next, the second element, 2, is compared with the first element. Since 2 is smaller, it is moved to the left of 3, resulting in the array [2, 3, 5, 4, 1].
3. Now, the third element, 5, is compared with the sorted elements to its left. It remains in its position since it is already larger than 2 but smaller than 3.
4. The fourth element, 4, is inserted to its correct position by shifting 5 to the right, resulting in [2, 3, 4, 5, 1].
5. Finally, the fifth element, 1, is compared with the sorted elements to its left and inserted to its correct position, resulting in the sorted array [1, 2, 3, 4, 5].

So, the contents of the array during the insertion sort process are:

1. [3, 2, 5, 4, 1] (Initial array)
2. [2, 3, 5, 4, 1]
3. [2, 3, 5, 4, 1]
4. [2, 3, 4, 5, 1]
5. [1, 2, 3, 4, 5] (Sorted array)