/**
 * Find Nth smallest/largest(?) element in the list without sorting.
 */
package classnotes;

import java.util.Arrays;

public class QuickSortSeq {

	public static int MAX = 8;
	public static int count = 0;
	public static int countComp = 0;

	static int partition(int arr[], int lo, int hi) {
		int i = lo, j = hi;
		int tmp;
		// int pivot = arr[(lo + hi) / 2];
		int pivot = arr[lo];

		for (; i < j;) {
			for (countComp++; arr[i] < pivot; i++, countComp++)
				;
			for (countComp++; arr[j] > pivot; j--, countComp++)
				;
			if (i < j) {
				countComp++;
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				i++;
				j--;
			}
		}
		return i;
	}

	public static void quickSort(int a[]) {
		quickSort(a, 0, a.length - 1);
	}

	public static void printArrayPivot(int a[], int lo, int hi, int p) {
		System.out.print("array: ");
		if (p > lo) {
			System.out.print(" [");
			for (int i = lo; i < p; i++)
				System.out.print(" " + a[i]);
			System.out.print("] ");
		}
		System.out.print(a[p]);
		if (hi > p) {
			System.out.print(" [");
			for (int i = p + 1; i <= hi; i++)
				System.out.print(" " + a[i]);
			System.out.print("]");
		}
		System.out.println();
	}

	public static void printArray(int a[], int lo, int hi) {
		int l[] = new int[MAX];
		for (int i = lo; i < hi; i++)
			l[i] = a[i];

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

	public static void quickSort(int arr[], int lo, int hi) {
		if (lo < hi) {

			int pivot = partition(arr, lo, hi);
			// printArrayPivot(arr, lo, hi, pivot);
			quickSort(arr, lo, pivot - 1);
			quickSort(arr, pivot + 1, hi);
		}
	}

	public static void main(String[] args) {
		// System.out.println("(len,count,nln,n2)");
		// for (int k = 1; k < 100; k++) {
		MAX = 15;
		int x[] = new int[MAX];
		for (int i = 0; i < x.length; i++)
			// x[i] = (int) (Math.random() * 100) % 100;
			x[i] = MAX - i;
		// System.out.rintln(Arrays.toString(x));
		// System.out.println();
		quickSort(x);
		// System.out.println();
		// System.out.println(Arrays.toString(x));
		System.out.println(countComp + "," + (int) (MAX * Math.log10(MAX) / Math.log10(2)) + "," + MAX * MAX);
		// int nln = (int) (k * Math.log10(k) / Math.log10(2));
		// int n2 = (int) (k * k);
		// System.out.print("(" + k + "," + countComp + "," + nln + "," + n2
		// +")");
		// if (countComp > n2)
		// System.out.println("worst");
		// else if (countComp > nln)
		// System.out.println("average");
		// else if (countComp <= nln)
		// System.out.println("best");
		// else
		// System.out.println();
		// }
	}
}