quickSort.java

public class quickSort {
	
	public static void main(String args[]){
		int[] array = new int[]{2,1,6,4,8,7};
		int i=0;
		quickSort q = new quickSort();
		q.Sort(array);
		for(i=0;i<array.length;i++){
			System.out.println(array[i]);
		}
	}
	
	public void Sort(int array[]) 
	// pre: array is full, all elements are non-null integers
	// post: the array is sorted in ascending order
	{
		quickSort(array, 0, array.length - 1);              // quicksort all the elements in the array
	}


	public void quickSort(int array[], int start, int end)
	{
	        int i = start;                          // index of left-to-right scan
	        int k = end;                            // index of right-to-left scan

	        if (end - start >= 1)                   // check that there are at least two elements to sort
	        {
	                int pivot = array[start];       // set the pivot as the first element in the partition

	                while (k > i)                   // while the scan indices from left and right have not met,
	                {
	                        while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
	                                i++;                                    // element greater than the pivot
	                        while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
	                            k--;                                        // element not greater than the pivot
	                        if (k > i)                                       // if the left seekindex is still smaller than
	                                swap(array, i, k);                      // the right index, swap the corresponding elements
	                }
	                swap(array, start, i-1);          // after the indices have crossed, swap the last element in
	                                                // the left partition with the pivot 
	                quickSort(array, start, k - 1); // quicksort the left partition
	                quickSort(array, k + 1, end);   // quicksort the right partition
	        }
	        else    // if there is only one element in the partition, do not do any sorting
	        {
	                return;                     // the array is sorted, so exit
	        }
	}

	public void swap(int array[], int index1, int index2) 
	// pre: array is full and index1, index2 < array.length
	// post: the values at indices 1 and 2 have been swapped
	{
		System.out.println("Swapping"+array[index1]+" with"+array[index2]);
		int temp = array[index1];           // store the first value in a temp
		array[index1] = array[index2];      // copy the value of the second into the first
		array[index2] = temp;               // copy the value of the temp into the second
	}

}