Quick Sort Algorithm

Quick Sort Algorithm is one has a really good average runtime it is based on divide and conquer it takes particular element as an pivot and Perform partitions the given array around the picked pivot.

Press enter or click to view image in full size

Get Pandiyan Mani’s stories in your inbox

Join Medium for free to get updates from this writer.

Subscribe

Subscribe

Remember me for faster sign in

Best Case: The best case occurs when the partition process always picks the middle element as pivot. Following is recurrence for best case.

T(n) = 2T(n/2) + 0(n)

Lets see an example on QuickSort Algorithm

public class MyClass {
    public static void main(String args[]) {
        int numbers[] = {5,4,3,9,8,6,8};
        quicksort(numbers,0,numbers.length-1);

        for(int i=0;i<numbers.length;i++) {
            System.out.println(numbers[i]);
        }

    }

    private static void quicksort(int numbers[],int lowIndex,int highIndex) {
        if(lowIndex < highIndex) {

            int pivot = numbers[highIndex];
            int LP = lowIndex;
            int RP = highIndex;

            while(LP < RP) {

                while(numbers[LP] <= pivot && LP < RP) {
                    LP++;
                }
                while(numbers[RP] >= pivot && LP < RP) {
                    RP--;
                }

                swap(numbers,LP,RP);
            }

            swap(numbers,LP,highIndex);
            quicksort(numbers,lowIndex,LP-1);
            quicksort(numbers,LP+1,highIndex);

        }

    }

    private static void swap(int numbers[],int index1,int index2) {
        int temp = numbers[index1];
        numbers[index1] = numbers[index2];
        numbers[index2] = temp;
    }
}