Quicksort.java

import java.util.concurrent.ThreadLocalRandom;
import java.util.Arrays;

/**
 * Quicksort implementation that counts that
 * number of comparisons required to perform the sort.
 *
 * @author Jabari Dash
 */
public class QuickSort {

//------------------------------------------------------------------------------

  /**
   * Display an array on a new line.
   *
   * @param a Array to display.
   */
  private static void display(int[] a) {

    System.out.println(Arrays.toString(a));
  }

//------------------------------------------------------------------------------

  /**
   * Swaps two values in an
   * array by index.
   *
   * @param a Array.
   * @param i First index.
   * @param j Second index.
   *
   */
  private static void swap(int[] a, int i, int j) {

    int t = a[i];

    a[i] = a[j];
    a[j] = t;
  }

//------------------------------------------------------------------------------

  /**
   * Shuffles an array.
   *
   * @param a Array to shuffle.
   */
  private static void shuffle(int[] a) {

    int j;

    for (int i = a.length - 1; i >= 0; i--) {

      j = ThreadLocalRandom.current()
                           .nextInt(0, i + 1);

      swap(a, i, j);
    }
  }

//------------------------------------------------------------------------------

  /**
   * Sorts an array using quicksort.
   *
   * @param a Array to sort.
   *
   * @return Number of data comparisons.
   */
  private static int quicksort(int[] a) {

    return quicksort(a, 0, a.length - 1);
  }

//------------------------------------------------------------------------------

  /**
   * Sorts a sub-array using quicksort.
   *
   * @param a Array to sort.
   * @param lo Left bound.
   * @param hi Right bound.
   *
   * @return Number of data comparisons.
   */
  private static int quicksort(int[] a, int lo, int hi) {

    var c = 0;

    if (lo >= hi)
      return c;

    var i     = lo;
    var j     = hi;
    var r     = ThreadLocalRandom.current().nextInt(lo, hi + 1);
    var pivot = a[r];

    while (i <= j) {

      while (a[i] < pivot) {
        i++;
        c++;
      }

      while (a[j] > pivot) {
        j--;
        c++;
      }

      if (i <= j) {
        
        swap(a, i, j);

        i++;
        j--;
      }
    }

    if (lo < j)
      c += quicksort(a, lo, j);

    if (i < hi)
      c += quicksort(a, i, hi);

    return c;
  }

//------------------------------------------------------------------------------

  /**
   * Initializes an array such that
   * every value is equal to it's index.
   *
   * @param a Array to initialize.
   */
  private static void init(int[] a) {

    for (int i = 0; i < a.length; i++)
      a[i] = i;
  }

//------------------------------------------------------------------------------

  public static void main(String[] args) {

    int c;

    int min       = 50;
    int max       = 5000;
    int increment = 50;

    int[] a;

    System.out.println("n\tE(n)\tE(n)/n^2\tE(n)/n*log(n)");

    for (int i = min; i <= max; i += increment) {

      a = new int[i];

      init(a);

      shuffle(a);

      c = quicksort(a);

      System.out.format("%d\t%d\t%f\t%f\n",
        i,
        c,
        c / Math.pow(i, 2),
        c / i * (Math.log(i) / Math.log(2))
      );

    }
  }
}