Monday, May 12, 2014

QuickSort in Java

public class QuickSort
{
    public static void main(String args[])
    {

        int arr[] = { 5, 4, 3, 2, 1 };

        quickSort(arr, 0, 4);
        System.out.println("Output");
        for (int i : arr)
            System.out.println(i);
    }

    public static void quickSort(int arr[], int f, int l)
    {
        int j;
        if (f < l)
        {
            j = partition(arr, f, l);
            quickSort(arr, f, j - 1);
            quickSort(arr, j + 1, l);
        }
    }

    public static int partition(int arr[], int f, int l)
    {
        int pivot = arr[f];

        int i = f;
        int j = l;
        int temp;

        while (i < j)
        {
            while (arr[i] <= pivot && i < l)
                i++;
            while (arr[j] > pivot && j > f)
                j--;

            if (i < j)
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

            }
        }

        temp = arr[f];
        arr[f] = arr[j];
        arr[j] = temp;

        return j;
    }
}