1(7 points)
Sort the array
| 3 | 7 | 6 | 5 | 1 | 4 | 8 | 2 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | index |
| 3 | 7 | 6 | 5 | 1 | 4 | 8 | 2 | original array |
| 3 | 7 | 6 | 5 | 1 | 4 | 8 | 2 | 7 left in position 1 |
| 3 | 6 | 7 | 5 | 1 | 4 | 8 | 2 | 6 moved before 7 |
| 3 | 5 | 6 | 7 | 1 | 4 | 8 | 2 | 5 moved before 6 |
| 1 | 3 | 5 | 6 | 7 | 4 | 8 | 2 | 1 moved before 3 |
| 1 | 3 | 4 | 5 | 6 | 7 | 8 | 2 | 4 moved before 5 |
| 1 | 3 | 4 | 5 | 6 | 7 | 8 | 2 | 8 left in place |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 2 moved before 3 |
2(6 points)
Write a recursive
function
int S(int A[], int size)that returns the sum of
A[0] + A[1] + A[2] + . . . + A[size - 1].
int S(int A[], int size){
// precondition: size >= 1; A has at least size values
if (size == 1) return A[0];
return A[size - 1] + S(A, size -1);
}
3(7 points)
The idea of the partition in QuickSort is:
A. Run a subloop to increase I until a large element is found
B. Run a subloop to decrease J until a small element is found
C. If it happens that I ² J after steps A and B then:
Show the work of the partition function
on the array below.
a. M = 3 b. X = 5 c. Show the contents of the array after each swap d. What are the values of I and J when the partition is finished?
J = 3
I = 4
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | index |
| 3 | 7 | 6 | 5 | 1 | 4 | 8 | 2 | original array |
| 3 | 2 | 6 | 5 | 1 | 4 | 8 | 7 | I = 1, J = 7 7 and 2 are swapped |
| 3 | 2 | 4 | 5 | 1 | 6 | 8 | 7 | I = 2, J = 5 6 and 4 are swapped |
| 3 | 2 | 4 | 1 | 5 | 6 | 8 | 7 | I = 3, J = 4 5 and 1 are swapped |
Last Updated: May 6, 1997 7:50 am by