1 Here is a short data set Show the contents in the array af

1. Here is a short data set. Show the contents in the array after each of the steps in sorting this data using an insertion sort, by adding more rows to the table.

8 2 3 5 3 1 7 4 5 9 8 2 3 5 3 1 7 4 5 9

2. Here is a short data set. Show the contents in the array after each of the steps in sorting this data using a selection sort, by adding more rows to the table.

8 2 3 5 3 1 7 4 5 9 8 2 3 5 3 1 7 4 5 9

3. Here is a short data set. Show the contents in the array after each of the steps in sorting this data using a merge sort, by adding more rows to the table.

8 2 3 5 3 1 7 4 5 9 8 2 3 5 3 1 7 4 5 9

4. Here is a short data set. Show the contents in the array after each of the steps in sorting this data using a quick sort, by adding more rows to the table.

8 2 3 5 3 1 7 4 5 9 8 2 3 5 3 1 7 4 5 9

Solution

INSERTION SORT
Iteration: 1
Array: [2, 8, 3, 5, 3, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 2
Array: [2, 3, 8, 5, 3, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 3
Array: [2, 3, 5, 8, 3, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 4
Array: [2, 3, 3, 5, 8, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 5
Array: [1, 2, 3, 3, 5, 8, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 6
Array: [1, 2, 3, 3, 5, 7, 8, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 7
Array: [1, 2, 3, 3, 4, 5, 7, 8, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 8
Array: [1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 9
Array: [1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 10
Array: [1, 2, 3, 3, 4, 5, 5, 7, 8, 8, 9, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 11
Array: [1, 2, 2, 3, 3, 4, 5, 5, 7, 8, 8, 9, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 12
Array: [1, 2, 2, 3, 3, 3, 4, 5, 5, 7, 8, 8, 9, 5, 3, 1, 7, 4, 5, 9]
Iteration: 13
Array: [1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 7, 8, 8, 9, 3, 1, 7, 4, 5, 9]
Iteration: 14
Array: [1, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 7, 8, 8, 9, 1, 7, 4, 5, 9]
Iteration: 15
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 7, 8, 8, 9, 7, 4, 5, 9]
Iteration: 16
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 7, 7, 8, 8, 9, 4, 5, 9]
Iteration: 17
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 7, 7, 8, 8, 9, 5, 9]
Iteration: 18
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
Iteration: 19
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
Sorted array is:
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]

SELECTION SORT
Iteration: 0
Array: [1, 2, 3, 5, 3, 8, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
Iteration: 1
Array: [1, 1, 3, 5, 3, 8, 7, 4, 5, 9, 8, 2, 3, 5, 3, 2, 7, 4, 5, 9]
Iteration: 2
Array: [1, 1, 2, 5, 3, 8, 7, 4, 5, 9, 8, 3, 3, 5, 3, 2, 7, 4, 5, 9]
Iteration: 3
Array: [1, 1, 2, 2, 3, 8, 7, 4, 5, 9, 8, 3, 3, 5, 3, 5, 7, 4, 5, 9]
Iteration: 4
Array: [1, 1, 2, 2, 3, 8, 7, 4, 5, 9, 8, 3, 3, 5, 3, 5, 7, 4, 5, 9]
Iteration: 5
Array: [1, 1, 2, 2, 3, 3, 7, 4, 5, 9, 8, 8, 3, 5, 3, 5, 7, 4, 5, 9]
Iteration: 6
Array: [1, 1, 2, 2, 3, 3, 3, 4, 5, 9, 8, 8, 7, 5, 3, 5, 7, 4, 5, 9]
Iteration: 7
Array: [1, 1, 2, 2, 3, 3, 3, 3, 5, 9, 8, 8, 7, 5, 4, 5, 7, 4, 5, 9]
Iteration: 8
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 9, 8, 8, 7, 5, 5, 5, 7, 4, 5, 9]
Iteration: 9
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 8, 8, 7, 5, 5, 5, 7, 9, 5, 9]
Iteration: 10
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 8, 7, 8, 5, 5, 7, 9, 5, 9]
Iteration: 11
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 7, 8, 8, 5, 7, 9, 5, 9]
Iteration: 12
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 8, 8, 7, 7, 9, 5, 9]
Iteration: 13
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 7, 7, 9, 8, 9]
Iteration: 14
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 8, 7, 9, 8, 9]
Iteration: 15
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 9, 8, 9]
Iteration: 16
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 9, 8, 9]
Iteration: 17
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
Iteration: 18
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
Iteration: 19
Array: [1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
Sorted array is:
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]

MERGE SORT
[8, 2, 3, 5, 3, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 8, 3, 5, 3, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 8, 3, 3, 5, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 8, 3, 3, 5, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 8, 3, 3, 5, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 8, 3, 3, 5, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 4, 5, 7, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 3, 5, 8, 1, 4, 5, 7, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 8, 3, 5, 3, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 8, 3, 3, 5, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 8, 3, 3, 5, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 8, 3, 3, 5, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 8, 3, 3, 5, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 7, 4, 5, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 4, 5, 7, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 2, 3, 3, 5, 8, 1, 4, 5, 7, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 1, 2, 3, 3, 4, 5, 5, 7, 8, 9]
[1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 1, 2, 3, 3, 4, 5, 5, 7, 8, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
Sorted array is:
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]

QUICK SORT
[8, 2, 3, 5, 3, 1, 7, 4, 5, 9, 8, 2, 3, 5, 3, 1, 7, 4, 5, 9]
[2, 3, 5, 3, 1, 4, 5, 2, 3, 5, 3, 1, 4, 5, 8, 8, 7, 7, 9, 9]
[2, 3, 3, 1, 4, 2, 3, 3, 1, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 3, 2, 4, 2, 3, 3, 3, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 3, 2, 4, 2, 3, 3, 3, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 3, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 3, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 3, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 8, 8, 7, 7, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]
Sorted array is:
[1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 8, 9, 9]