import java.util.Arrays;

/* Java class having methods to sort an array (or segment thereof) of int
** values using (the recursive version of) C.A.R. Hoare's QuickSort algorithm.
** The methods are "narrated" for the purpose of illustrating the sequence
** of steps that occur during execution (and the depth to which recursion
** has descended at each step).
** The code segments in between the comments marking the beginning and
** ending of the "entering" and "exiting" narration code blocks are there
** strictly for the purpose of providing narration.
**
** Author: R. McCloskey
** Date: April 2025
*/

public class QuickSortInt {

   private static int depth = -1;

   public static void quickSort(int[] a) {
      quickSort(a, 0, a.length);
      System.out.println(Arrays.toString(a));
   }

   /* Rearranges the elements of the given array segment (a[low..high))
   ** to place them into ascending order.
   */
   public static void quickSort(int[] a, int low, int high) {
      // start of entering narration
      depth++;
      printSpaces(2*depth);
      System.out.printf("About to sort a[%d..%d): ", low, high);
      printArySeg(a,low,high);
      // end of entering narration

      if (high-low < 2) { }  // base case: segment of length < 2
      else {
         int k = partition(a,low,high);
         // assert: Every element in a[low..k) is < a[k] and
         //         every element in a[k+1..high) is >= a[k]
         quickSort(a,0,k);
         quickSort(a,k+1,high);
      } 

      // start of exiting narration
      printSpaces(2*depth);
      System.out.printf("Done sorting a[%d..%d): ", low, high);
      printArySeg(a,low,high);
      depth--;
      // end of exiting narration

   }
   
   /* Partitions array segment a[low..high) wrt to some pivot value
   ** chosen from within.
   ** Value returned is k satisfying low <= k < high, with all elements in
   ** a[low..k) being < a[k] and all elements in a[k+1..high) being >= a[k].
   ** pre: 0 <= low < high <= a.length
   */
   private static int partition(int[] a, int low, int high) {

      // start of entering narration
      depth++;
      printSpaces(2*depth);
      System.out.printf("About to partition a[%d..%d): ", low, high);
      printArySeg(a,low,high);
      // end of entering narration

      int pivot = a[high-1];
      int j = low, k = low;
      // loop invariant:
      //   all elements in a[low..j) are < pivot
      //   and all elements in a[j..k) are >= pivot
      while (k != high-1) {
         if (a[k] >= pivot) { k = k+1; }
         else {  // a[k] < pivot
            swap(a, j, k);
            j++; k++;
         }
      }
      // Now place the pivot (sitting in location high-1) into its
      // rightful place, location j.
      swap(a, j, high-1);

      // start of exiting narration
      printSpaces(2*depth);
      System.out.printf("Done partitioning a[%d..%d): ", low, high);
      printArySeg(a,low,high);
      depth--;
      // end of exiting narration

      return j;
   }

   /* Swaps the values in the specified locations of the specified array.
   */
   private static void swap(int[] b, int i, int j) {
      int temp = b[i];
      b[i] = b[j];
      b[j] = temp;
   }

   private static void printArySeg(int[] b, int low, int high) {
      System.out.print('[');
      for (int r = low; r != high; r++) {
         System.out.printf("%d:%d ", r, b[r]);
      }
      System.out.println(']');
   }

   private static void printSpaces(int num) {
      for (int r=0; r != num; r++) {
         System.out.print(' ');
      }
   }
   
   public static void main(String[] args) {
      int[] ary = new int[] { 5, 13, -2, 6, 23, 18, 5, 12, 0, 4, 11 };
      quickSort(ary);
   }
   
}