On line 4 of the code for insertionSort() (Figure 8-8) we store data[i] in a sep
ID: 3566017 • Letter: O
Question
On line 4 of the code for insertionSort() (Figure 8-8) we store data[i] in a separate variable target . The version in Figure 8-9 omits this "redundant" variable. Explain why it doesn't work.
Figure 8-9. Broken version of insertionSort() for Exercise 8.6.
1 /** Arrange the numbers in data from smallest to largest. */
2 public static void insertionSort(int[] data) {
3 for (int i = 1; i < data.length; i++) {
4 int j;
5 for (j = i - 1; (j >= 0) && (data[j] > data[i]); j--) {
6 data[j + 1] = data[j];
7 }
8 data[j + 1] = data[i];
9 }
10 }
Figure 8-8. Code for insertionSort() .
1/** Arrange the numbers in data from smallest to largest. */
2 public static void insertionSort(int[] data) {
3 for (int i = 1; i < data.length; i++) {
4 int target = data[i];
5 int j;
6 for (j = i - 1; (j >= 0) && (data[j] > target); j--) {
7 data[j + 1] = data[j];
8 }
9 data[j + 1] = target;
10 }
11 }
On line 4 of the code for insertionSort() (Figure 8-8) we store data[i] in a separate variable target . The version in Figure 8-9 omits this "redundant" variable. Explain why it doesn't work.
Figure 8-9. Broken version of insertionSort() for Exercise 8.6.
1 /** Arrange the numbers in data from smallest to largest. */
2 public static void insertionSort(int[] data) {
3 for (int i = 1; i < data.length; i++) {
4 int j;
5 for (j = i - 1; (j >= 0) && (data[j] > data[i]); j--) {
6 data[j + 1] = data[j];
7 }
8 data[j + 1] = data[i];
9 }
10 }
Explanation / Answer
Let us consider a particular exampe : data = [1, 7, 10, 12, 9]. Since data[0],...,data[3] are in order, the first time when the inner for-loop is entered, is when i = 4.
Run of the correct version when i = 4:
target = 9
(In the inner for-loop)
j=3: data = [1,7,10,12,12]
j=2: data = [1, 7, 10, 10, 12]
(out of the inner for-loop)
data[2] = 9 (we saved the value of target !)
data = [1,7,9,10,12]
Run of the broken version when i = 4:
(In the inner for-loop)
j=3: data = [1,7,10,12,12]
j=2: data = [1, 7, 10, 10, 12]
(out of the inner for-loop)
data[2] = 12 (the original value was overriden !)
data = [1,7,12,10,12]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.