//for reference public ArrayList SelectionSortExampleList() { ArrayList answer = new ArrayList(); answer.add(new int[] {-1, 20, 18, 17, 9, 4, 2, 0, 40}); answer.add(new int[] {-1, 0, 18, 17, 9, 4, 2, 20, 40}); answer.add(new int[] {-1, 0, 2, 17, 9, 4, 18, 20, 40}); answer.add(new int[] {-1, 0, 2, 4, 9, 17, 18, 20, 40}); answer.add(new int[] {-1, 0, 2, 4, 9, 17, 18, 20, 40}); answer.add(new int[] {-1, 0, 2, 4, 9, 17, 18, 20, 40}); // etc... (the rest of the iterations) return answer; } Make sure to write ALL the iterations, even the ones that look like duplicate lines. (For the sake of brevity, we are not showing all of them here.) For insertion sort tracing, you should have the same number of iterations as the number of elements in the list (including the initial array as the first "iteration"). For quick sort tracing, select the pivot element as the first element in the subarray. For merge sort tracing, you may assume that the array is given to you in the final-split step. In other words, you can start from the elements being split into single-element arrays and write the merges that occur thenceforth. through the iterations of the insertion sort, quick sort, and merge sort algorithms for each of the three input arrays (9 traces total). Your answer should be in Sorts Tracing.java, where each iteration is added to an ArrayList, which is returned by the corresponding method. The original array is already added for you as the first line of each method. You do not need to add it again. For example, for selection sort on the list [40, 20, 18, 17, 9, 4, 2, 0, -1], the list of iterations looks like this (sorted elements are given in blue for readability): Initial Array [40, 20, 18, 17, 9, 4, 2, 0, -1] Iteration 1 [-1, 20, 18, 17, 9, 4, 2, 0, 40] Iteration 2 [-1, 0, 18, 17, 9, 4, 2, 20, 40] Iteration 3 [-1, 0, 2, 17, 9, 4, 18, 20, 40] Iteration 4 [-1, 0, 2, 4, 9, 17, 18, 20, 40] Iteration 5 [-1, 0, 2, 4, 9, 17, 18, 20, 40] Iteration final [-1, 0, 2, 4, 9, 17, 18, 20, 40] In the file SortsTracing.java, the method would look like this:
starter code
import java.util.ArrayList;
public class SortsTracing {
//Note: Style is not required for this file
//for reference
public ArrayList<int[]> SelectionSortExampleList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{-1, 20, 18, 17, 9, 4, 2, 0, 40});
answer.add(new int[]{-1, 0, 18, 17, 9, 4, 2, 20, 40});
answer.add(new int[]{-1, 0, 2, 17, 9, 4, 18, 20, 40});
answer.add(new int[]{-1, 0, 2, 4, 9, 17, 18, 20, 40});
answer.add(new int[]{-1, 0, 2, 4, 9, 17, 18, 20, 40});
answer.add(new int[]{-1, 0, 2, 4, 9, 17, 18, 20, 40});
// etc... (the rest of the iterations)
return answer;
}
public ArrayList<int[]> InsertionSortRandomList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{30, 62, 5, 109, 66, 17, 51, 18});
// TODO
return answer;
}
public ArrayList<int[]> InsertionSortSortedList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{5, 17, 18, 30, 51, 62, 66, 109});
// TODO
return answer;
}
public ArrayList<int[]> InsertionSortReversedList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{109, 66, 62, 51, 30, 18, 17, 5});
// TODO
return answer;
}
public ArrayList<int[]> MergeSortRandomList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{88, 46, -1, 8, 100, -2, 38, 16});
// TODO
return answer;
}
public ArrayList<int[]> MergeSortSortedList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{-2, -1, 8, 16, 38, 46, 79, 100});
// TODO
return answer;
}
public ArrayList<int[]> MergeSortReversedList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{100, 88, 46, 38, 16, 8, -1, -2});
// TODO
return answer;
}
public ArrayList<int[]> QuickSortRandomList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{12, 0, 67, -8, 54, 53, 95, 22});
// TODO
return answer;
}
public ArrayList<int[]> QuickSortSortedList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{-8, 0, 12, 22, 53, 54, 67, 95});
// TODO
return answer;
}
public ArrayList<int[]> QuickSortReversedList() {
ArrayList<int[]> answer = new ArrayList<int[]>();
answer.add(new int[]{95, 67, 54, 53, 22, 12, 0, -8});
// TODO
return answer;
}
}
![//for reference
public ArrayList<int[]> SelectionSortExampleList() {
ArrayList<int[] > answer = new ArrayList<int[]>();
answer.add(new int[] {-1, 20, 18, 17, 9, 4, 2, 0, 40});
answer.add(new int[] {-1, 0, 18, 17, 9, 4, 2, 20, 40});
answer.add(new int[] {-1, 0, 2, 17, 9, 4, 18, 20, 40});
answer.add(new int[] {-1, 0, 2, 4, 9, 17, 18, 20, 40});
answer.add(new int[] {-1, 0, 2, 4, 9, 17, 18, 20, 40});
answer.add(new int[] {-1, 0, 2, 4, 9, 17, 18, 20, 40});
// etc... (the rest of the iterations)
return answer;
}
Make sure to write ALL the iterations, even the ones that look like duplicate lines.
(For the sake of brevity, we are not showing all of them here.)
For insertion sort tracing, you should have the same number of iterations as the
number of elements in the list (including the initial array as the first "iteration").
For quick sort tracing, select the pivot element as the first element in the subarray.
For merge sort tracing, you may assume that the array is given to you in the final-split
step. In other words, you can start from the elements being split into single-element
arrays and write the merges that occur thenceforth.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F5483afab-7850-40f6-959f-e698dea1419a%2Febcec92a-b267-4f34-8ba0-f412bf28818a%2F8sx1vfq_processed.png&w=3840&q=75)
![through the iterations of the insertion sort, quick sort, and merge sort algorithms for each
of the three input arrays (9 traces total).
Your answer should be in Sorts Tracing.java, where each iteration is added to an ArrayList,
which is returned by the corresponding method. The original array is already added for you
as the first line of each method. You do not need to add it again.
For example, for selection sort on the list [40, 20, 18, 17, 9, 4, 2, 0, -1], the list of iterations
looks like this (sorted elements are given in blue for readability):
Initial Array
[40, 20, 18, 17, 9, 4, 2, 0, -1]
Iteration 1
[-1, 20, 18, 17, 9, 4, 2, 0, 40]
Iteration 2
[-1, 0, 18, 17, 9, 4, 2, 20, 40]
Iteration 3
[-1, 0, 2, 17, 9, 4, 18, 20, 40]
Iteration 4
[-1, 0, 2, 4, 9, 17, 18, 20, 40]
Iteration 5
[-1, 0, 2, 4, 9, 17, 18, 20, 40]
Iteration final
[-1, 0, 2, 4, 9, 17, 18, 20, 40]
In the file SortsTracing.java, the method would look like this:](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F5483afab-7850-40f6-959f-e698dea1419a%2Febcec92a-b267-4f34-8ba0-f412bf28818a%2Fm5nr23_processed.png&w=3840&q=75)
Step by step
Solved in 2 steps
