Partition Array

Partition an Array with a pivot is NON trivial

Given an array of integer int[] arr = {2, 1, 4, 3, 2}, choose a pivot, and partition the array into left and right so that all the number on the left is less or qual to the pivot and all the number on the right is greater than the pivot

    int[] arr = {2, 1, 4, 3, 2}

    1. Choose last element as pivot → 2
    2. left array  {2, 1, 3}   less or equal than pivot
    3. right array {4}         greater than pivot


    → {2, 1, 3}  {2}    {4}
         left   pivot   right

    Best Approach 1 with BUG: Use only swap operation

NOTE: The approach contains a BUG if you use the following function inside your Quick Sort This approach does not need temporary buffer. It only uses swap operation

    public static int partitionArr(Integer[] arr, int lo, int hi){
        int len = arr.length;
        int bigInx = lo;
        Integer pivot = arr[hi];
        for(int i = 0; i < len; i++){
            if(arr[i] <= pivot){
                int tmp = arr[i];
                arr[i] = arr[bigInx];
                arr[bigInx] = tmp;

                if(i < len - 1)
                    bigInx++;
            }
        }
        return bigInx;
    }

    Best Approach 1 with NO BUG: Use only swap operation

    public static int partitionArr2(Integer[] arr, int lo, int hi){
        int len = arr.length;
        int bigInx = lo;
        Integer pivot = arr[hi];
        for(int i = lo; i <= hi; i++){
            if(arr[i] <= pivot){
                int tmp = arr[i];
                arr[i] = arr[bigInx];
                arr[bigInx] = tmp;
                if(i < hi)
                    bigInx++;
            }
        }
        return bigInx;
    }

We can use above partitionArr2 on Quick Sort Algorithm.

The idea is similar as preOrder traveral

    public static void quickSort(Integer[] arr, int lo, int hi){
        if(lo < hi){
            int pivotInx = partitionArr2(arr, lo, hi);
            quickSort(arr, lo, pivotInx - 1);
            quickSort(arr, pivotInx + 1, hi);
        }
    }

Approach 2, Use a tmp array

0. Create temporary array with same length as original array 1. Choose the most right element as pivot 2. Create left index and right index 3. Iterate through the origin array 1. If the element is less or equal the pivot 1. add the element to the left side of temporary array else add the element to the right side of temporary array

    int partition(int[] arr, int lo, int hi){
      int len = arr.length;
      int pivot = arr[hi];  // use last elem as pivot
      int[] retArr = new int[len];  
      int leftInx = 0;        // leftInx++ =>
      int rightInx = len - 1; // rightInx-- <=
      int k = lo;
      while(leftInx != rightInx){
         retArr[arr[k] <= pivot ? leftInx++ : rightInx--] = arr[k++];
      }

      // pivot index == leftInx == rightInx
      // pivot position
      retArr[leftInx] = pivot

      // copy retArr back to arr
      for(int i = 0; i < len; i++){
          arr[lo + i] = retArr[i];
      } 
    return leftInx;
  }