import java.awt.*;

public class QuickSort extends ShowSort {
	Color pivot_bar_color = Color.green;
	
	int piv=0;
	
	public static void main(String args[]) {
		QuickSort applet = new QuickSort();
		applet.launch("QuickSort");
	}

	void doSort() {
		inplace_dir = true;
		inplace_pos = NUM;
		quickSort(array, 0, NUM-1);
		inplace_pos = 0;
		piv = -1;
	}

	void quickSort(int array[], int bottom, int top) {
		int pivot = partition(array, bottom, top);
		piv=pivot;
		if ((top-1) > pivot) {
			quickSort(array, pivot+1, top);
		}
		inplace_pos = pivot;
		if ((bottom+1) < pivot) {
			quickSort(array, bottom, pivot-1);
		}
	}

	int partition(int array[], int lo, int hi) {
		int pval = array[lo];
		while (lo < hi) {
			while (lo < hi && pval < array[hi]) {
				hi--;
				compared(hi);
			}
			if (hi != lo) {
				array[lo++] = array[hi];
				swapped(lo);
			}
		
			while (lo < hi && pval > array[lo]) {
				lo++;
				compared(lo);
			}
			if (hi != lo) {
				array[hi--] = array[lo];
				swapped(hi);
			}
		}

		array[hi] = pval;
		swapped(hi);
		
		return hi;
	}

	public void paint(Graphics g) {
		super.paint(g);
		if(0 <= piv && piv < NUM) {
			g.setColor(pivot_bar_color);
			drawBar(g,piv);
		}
	}
}