import java.util.Scanner;
import java.util.Random;
public class QuickSort{
    private static int count1 = 0, count2= 0;
    private static Random r1 = new Random();
    public static int partition(int a[], int left, int right){
        System.out.println ("Partition = " + left + "  " + right );
        int pivot = a[left];
        System.out.println ("Pivot = " + pivot);
        int l = left;
        left++;
        int count = 0;
        while (left <=right){
            count++;
            if (a[left] >= pivot && a[right] <= pivot){
                int temp = a[left];
                a[left] = a[right];
                a[right] = temp;
            }
            if (a[left] <= pivot){
                left++;
            }
            if (a[right] >= pivot){
                right--;
            }
        }
        int temp = a[l];
        a[l] = a[right];
        a[right] = temp;
        for (int i : a){
            System.out.print(i+ "  " );
        }
        System.out.println("\n");
        System.out.println ("Number of loops = " + count);
        count1 += count;
        return right ; 
    }

    public static void quicksort(int a[], int left, int right) {
        count2++;
        if (left < right){
            int pivot = partition(a, left, right);
            System.out.println ("Calling qsort " + left + "  " + (pivot-1) + "\n");
            quicksort(a, left, pivot-1);
            System.out.println ("Calling qsort " + (pivot +1) + "  " + right + "\n");
            quicksort(a, pivot+1, right);
        }
    }

    public static void main(String args[]){
        int a[] = {56,241,13, 23, 67, 223, 23, 1};
        System.out.print ("Starting Array:");
        for (int i =0; i<a.length; i++){ 
            System.out.print(a[i] + " ");
        } 
        System.out.println();
        quicksort(a, 0, a.length -1);
        System.out.println();
        for (int i =0; i<a.length; i++){ 
            System.out.print(a[i] + " ");
        } 
        System.out.println();
        System.out.println ("Partition = " + count1 + " Quicksort = " + count2);
    }
}