private static void insertionSort(int[] numbers) {
for (int i = 1; i < numbers.length; i++) {
int j = i;
while (j > 0 && numbers[j] < numbers[j - 1]) {
swap(numbers, j, j - 1);
j--;
}
}
}Trace the execution of insertion sort as it sorts the following sequence of records. In this case, the key is the number, and the superscript indicates the record.
\([7^A, 1^B, 11^C, 7^D, 1^E, 1^F]\)
After first iteration of outer loop:
\([\mathbf{1^B, 7^A}, 11^C, 7^D, 1^E, 1^F]\)
Was insertion sort stable in this case?
If so, is insertion sort always stable? Justify your answer.
private static void selectionSort(int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) {
int indexSmallest = i;
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[j] < numbers[indexSmallest]) {
indexSmallest = j;
}
}
swap(numbers, i, indexSmallest);
}
}Trace the execution of selection sort as it sorts the following sequence of records. In this case, the key is the number, and the superscript indicates the record.
\([7^A, 1^B, 11^C, 7^D, 1^E, 1^F]\)
Was selection sort stable in this case?
If so, is selection sort always stable? Justify your answer.
On average, insertion sort is faster than selection sort by a constant factor. Why? (Hint: Think about the worst, best, and average cases for each algorithm.)
Provide an example of a length-three worst case-input for insertion sort. How many comparisons will insertion sort perform on your input? How many swaps?
For the input you created above, how many comparisons will
selection sort perform? How many swaps?
Our textbook does not provide an exact analysis of the number of
comparisons for these sorting algorithms. Analyze insertion sort
by developing a summation that describes the number of comparisons
performed in the worst case. Solve the summation.
Here is the implementation of the swap operation used by the two algorithms above:
public void swap(int[] numbers, int i, int j) {
T tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}Notice that each swap operation requires three assignments. For this reason, most insertion sort implementations don’t call a swap method. Instead, they follow the following steps for each sorting pass:
Place the item being inserted into a temporary variable.
Iterate to the left, shifting each element to the right if it is
greater than the element being inserted. (This requires only one
assignment per item.)
Place the item into its final sorted position.Rewrite the insertion sort algorithm to use this approach.