Problem: Partition


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.

Definition

Class

public class QuickSort { private void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } /** * rearranges entries in array a to partition them such that small numbers * on at the front and large at the back * * @returns pivot such that * forall k, left <= k <= pivot, a[k] <= a[pivot] and * forall k, pivot < k <= right, a[pivot] < a[k] */ public void partition2 (int[] a) { // TODO: move around elements so that all elements // less than pivot are to the left of pivot value with // followed by all values equal // the order of the elements less than or equal to the pivot // should remain unchanged // You should maintain the following invariant // a[0...less] < pivot // a[less+1...k-1] > pivot // a[k...a.length-1] are unknown } }

Constraints

Examples

  1. [4, 3, 8, 9, 1, 6, 0, 5]
    Returns: [0, 3, 1, 4, 8, 6, 9, 5]

  2. [5, 10, 10, 4, 5, 6]
    Returns: [5, 4, 5, 10, 10, 6]

  3. [1, 10, 9, 7]
    Returns: [1, 10, 9, 7]




Example Solutions to Quicksort
Example answers to questions