// QuickSort Example

// Sort an array of integers with quicksort.
// Quicksort is a recursive algorithm.

public class QuickSort
{
    // Array to sort.
    private static int[ ] a =
        {31, 65, 27, 43, 73, 12, 96};

    public static void main(String[ ] args)
    {
        int i;

        // Print array before sorting.
        for(i = 0; i <= 6; i++)
            System.out.print(a[i] + " ");
        System.out.println();

        // Sort array with quicksort.
        quicksort(0, 6);

        // Print array after sorting.
        for(i = 0; i <= 6; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    // Quicksort algorithm.
    public static void quicksort(int i, int j)
    {
        int k;
        if (i < j)
        {
            k = partition(i, j);
            quicksort(i, k - 1);
            quicksort(k, j);
        }
    }

    // Partition array into two parts.
    // Every element in bottom part should
    // be smaller than every element in top part.
    public static int partition(int i, int j)
    {
        int pivot;
        pivot = a[(i + j) / 2];
        while(i <= j)
        {
            while (a[i] < pivot)
                i++;
            while (a[j] > pivot)
                j--;
            if (i <= j)
                swap(i++, j--);
        }
        return i;
    }

    // Swap elements
    public static void swap(int i, int j)
    {
        int temp;

        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}