Quick Sort- Algo 7

     Time Complexity Average/Best case- O(nlogn) Worst Case- O(n^2)

a)In Quicksort ,all the real work happens in the DIVIDE step. In fact, the COMBINE step in quicksort does absolutely nothing.

     b)Divide by choosing any element in the subarray array[p..r]. Call this element the pivot. Rearrange the elements in array[p..r] so that all other elements in array[p..r] that are less than or equal to the pivot are to its left and all elements in array[p..r] are to the pivot's right. We call this procedure partitioning. 

     c)  Conquer by recursively sorting the subarrays array[p..q-1] (all elements to the left of the pivot, which must be less than or equal to the pivot) andarray[q+1..r] (all elements to the right of the pivot, which must be greater than the pivot).

     d) Why does the pivot matter ?
On average quick sort runs in O(n log n) but if it consistently chooses bad pivots its performance degrades to O(n^2)
This happens if the pivot is consistently chosen so that all (or too many of) the elements in the array are < the pivot or > than the pivot.
(A classic case is when the first or last element is chosen as a pivot and the data is already sorted     ,or nearly sorted)

Java Implementation

package com.javatutorials.Sort;

public class QuickSort {

    public static void main(String[] args) {

         int[] array = new int[] {6,4,28,3,17,27,50,20,90,70,30};

         sort(array);

    }

    public static void sort(int[] array) {

         if (array == null || array.length == 0)

             return;

         int high = array.length;

         quickSort(array, 0, high - 1);

         for(int k=0;k<array.length;k++)

             System.out.println(array[k]);

        

    }

    // All real work done in divide step and combine steps hardly does anything...

    public static void quickSort(int[] array, int low, int high) {

         int i = low, j = high;

         int pivot = low + (high - low) / 2;

         while (i <= j) {

             /*

              * If the current value from the left list is smaller then the pivot

              * element then get the next element from the left list

              */

             while (array[i] < array[pivot])

                 i++;

             /*

              * If the current value from the right list is larger then the

              * pivot element then get the next element from the right list

              * */

             while (array[j] > array[pivot])

                 j--;

             if (i <= j) {

                 exchange(array, i, j);

                 i++;

                 j--;

             }

         }

         if (low < j)

             quickSort(array, low, j);

         if (i < high)

             quickSort(array, i, high);

    }

    public static void exchange(int array[], int i, int j) {

         int temp = array[i];

         array[i] = array[j];

         array[j] = temp;

    }

}

Output:

3   4   6   17  20  27  28  30  50  70  90