Consider the partition phase of the widely used sorting algorithm Quicksort that simply divides a given list of numbers so that all those less than a given value, called the pivot, are in the beginning of the array and all elements greater than the pivot are moved to the end. This algorithm is a classic example of where an invariant can help in developing the code and in reconstructing the code. An invariant is shown below pictorially (during the loop on the left and after the loop has finished on the right) and in the comments of the method partition2
below.
Note, there are many possible ways to rearrange the values in the array and correctly satisfy the goal of the algorithm, so your results may be correct and yet not pass the test cases provided. However, if you complete the method partition2
using the invariant given above and using the private method swap
to exchange the positions of two values, you should get the same results as the test cases. If your results do not match ours exactly, but your code reasonably partitions the numbers, you may still receive full credit.
[4, 3, 8, 9, 1, 6, 0, 5]Returns: [0, 3, 1, 4, 8, 6, 9, 5]
[5, 10, 10, 4, 5, 6]Returns: [5, 4, 5, 10, 10, 6]
[1, 10, 9, 7]Returns: [1, 10, 9, 7]