import java.util.Random;

/**
 * Quicksort() quickly sorts an array of integers.
 * @author Richard Nysäter
 * @version 2011-02-21
 */
public class Quicksort {
    /**
     * Sorts the array.
     * @param array the array to be sorted.
     */
    public void QuickSort(int[] array){
        qsort(array, 0, array.length-1);
    }


    private int partition(int[] arrayz, int first, int last) {
        int low = first, high = last;;
        int tmp;

        int pivot = arrayz[first];

        while (low <= high) {
            while(arrayz[low] < pivot){
                low++;
            }
            while(arrayz[high] > pivot){
                high--;
            }
            if (low < high) {
                tmp = arrayz[low];
                arrayz[low] = arrayz[high];
                arrayz[high] = tmp;
                low++;
                high--;
            }
        }
        return low;
    }

    private void qsort(int[] array, int first, int last) {

            int index = partition(array, first, last);

            if(first < index-1){
                qsort(array, first, index-1);
            }
            if(index < last){
                qsort(array, index+1, last);
            }
        }






}