tl  tr
  Home | Tutorials | Articles | Videos | Products | Tools | Search
Open Source | Tag Cloud | Follow Us | Bookmark | Contact   
 
 Data Structures > Sort > Quick Sort

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(n2)
  • 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  :  kvenkatasudhakar@gmail.com
   
package com.bethecoder.tutorials.ds.sort;

import java.util.Arrays;

public class QuickSort {

  /**
   @param args
   */
  public static void main(String[] args) {

    int[] list = 651839402711261219278619 };
    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 + endIndex2;
      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);
  }
}
   

It gives the following output,
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.


                    Print

   



Books Recommendation

 
 
bl  br