Quick Sort 

The following example shows quick sort implementation.

• Best case time complexity of quick sort is O(n log n)
• Worst case time complexity of quick sort is O(n²)
• Average case time complexity of quick sort is O(n log n)

File Name  :   com/bethecoder/tutorials/ds/sort/QuickSort.java  Author  :   Sudhakar KV Email  :   [email protected]

package com.bethecoder.tutorials.ds.sort; import java.util.Arrays; public class QuickSort {   /**    * @param args    */   public static void main(String[] args) {     int[] list = { 6, 5, 1, 8, 3, 9, 4, 0, 2, 7, 11, 26, 12, 19, 27, 86, 19 };     System.out.println("Before sort : " + Arrays.toString(list));     double timeTaken = quickSortTimeTaken(list);     System.out.println("After sort : " + Arrays.toString(list));     System.out.println("Time taken for QuickSort : " + timeTaken + " milliseconds.");   }   /**    * @param list    */   public static void quickSort(int[] list) {     quickSort(list, 0, list.length -1);   }      public static void quickSort(int[] list, int startIndex, int endIndex) {     int pivotValue, i, j, midIndex;     if (startIndex < endIndex) {       midIndex = (startIndex + endIndex) / 2;       pivotValue = list[midIndex];       i = startIndex;       j = endIndex;       while (i < j) {         //Get index of element which is greater than pivotValue         //in the first sublist         while ((i <= endIndex) && (list[i] < pivotValue)) {           i++;         }         //Get index of element which is less than pivotValue         //in the second sublist         while ((j >= startIndex) && (list[j] > pivotValue)) {           j--;         }         //Swap elements w.r.t pivotValue         if (i <= j) {           list[i] = list[i] + list[j] - (list[j] = list[i]);           i++;           j--;         }       }       //Recursively sort two sublists       quickSort(list, startIndex, j);       quickSort(list, i, endIndex);     }   }   /**    * Sorts and returns the time taken in milliseconds.    *     * @param list    * @return    */   public static double quickSortTimeTaken(int[] list) {     long startTime = System.nanoTime();     quickSort(list);     long timeTaken = System.nanoTime() - startTime;     return timeTaken * Math.pow(10, -6);   } }

Before sort : [6, 5, 1, 8, 3, 9, 4, 0, 2, 7, 11, 26, 12, 19, 27, 86, 19]
After sort : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 19, 19, 26, 27, 86]
Time taken for QuickSort : 0.00866 milliseconds.