// Tick 4 Part 1a.  Han-Ley Tang.

public class quickSort1a {

 public static void main(String[] args)
    {
	int[] myArray = {1,2,3,4,5,6,7,8,9,10};
	quicksort(myArray,0,myArray.length-1);
	for (int i = 0; i < myArray.length; i++)
		{ System.out.printf("%d,",myArray[i]); }
	}

public static void quicksort (int[] a)
	{
	quicksort(a, 0, a.length-1);
	}
 
 private static void quicksort (int[] a, int l, int r)
	{
	if ( l == r )				//list is empty
	return;
	int m = partition(a, l, r); //make partition and sort recursively
	quicksort(a,l,m-1);
	quicksort(a,m+1,r);
	}
 
//partition the array from l+1 to r with pivot a[l] 
private static int partition (int[] a, int l, int r)
	{
	int i=l+1;					//define left pointer
	int j=r;					//define right pointer
	int p = a[l];				//pivot element
	while (i<=j)				//move pointer to center or swap if on wrong sides
		{ 
		if (a[i]<=p) i++;
		else if (a[j]>p) j--;
		else swap(a,i,j);
		}
	swap(a,l,j);					//swap pivot element between partitions
	return j;
	}							//return position of pivot element

//swap two elements in the array
private static void swap (int[] a, int i, int j)
	{ 
	int h = a[i];
	a[i] = a[j];
	a[j] = h; }
	}