public class QuickSort {
   int[] array;
   int count;

   public QuickSort(int[] array) {
      this.array = array;
      count = 0;
   }

   public void swap(int i,int j) {
      int temporary = array[i];

      array[i] = array[j];
      array[j] = temporary;
   }

   public int partition(int first,int last) {
      int pivot = array[first];
      int lo = first;
      int hi = last;

      while (lo <= hi) {

         while ((lo <= last) && (array[lo] <= pivot)) {
            lo++;
            count++;
         }

         while (array[hi] > pivot) {
            hi--;
            count++;
         }

         if (lo < hi) {
            swap(lo,hi);
            lo++;
            hi--;
            count += 2;
         }
      }
   
      swap(first,hi);
      return hi;
   }

   public void quicksort(int first,int last) {
      int pivotIndex;

      if (first < last) {
         pivotIndex = partition(first,last);

         quicksort(first,pivotIndex-1);
         quicksort(pivotIndex+1,last);
      }
   }

   public void sort() {
      quicksort(0,array.length-1);
   }

   public String toString() {
      String output = "";

      for (int i=0;i<=array.length-1;i++) {
         output += String.valueOf(array[i]);
         output += "\t";
      }

      output += String.valueOf(count);

      return(output);
   }

   public static void main(String[] args) {
//      int[] array = {18,7,21,5,13,10,20};
      int[] array = {5,7,10,13,18,20,21};

      QuickSort myQuickSort = new QuickSort(array);

      System.out.println(myQuickSort);

      myQuickSort.sort();

      System.out.println(myQuickSort);
   }
}