Quicksort

Quicksort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n²) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.^[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort is acomparison sort and, in efficient implementations, is not a stable sort. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.^[2]

  // left is the index of the leftmost element of the subarray
  // right is the index of the rightmost element of the subarray (inclusive)
  // number of elements in subarray = right-left+1
  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right]  // Move pivot to end
     storeIndex := left
     for i from left to right - 1  // left ≤ i < right
         if array[i] <= pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right]  // Move pivot to its final place
     return storeIndex

 function quicksort(array, left, right)
     // If the list has 2 or more items
     if left < right
         // See "#Choice of pivot" section below for possible choices
         choose any pivotIndex such that left ≤ pivotIndex ≤ right
         // Get lists of bigger and smaller items and final position of pivot
         pivotNewIndex := partition(array, left, right, pivotIndex)
         // Recursively sort elements smaller than the pivot
         quicksort(array, left, pivotNewIndex - 1)
         // Recursively sort elements at least as big as the pivot
         quicksort(array, pivotNewIndex + 1, right)

package com.java2novice.sorting;

 

public class MyQuickSort {

     

    private int array[];

    private int length;

 

    public void sort(int[] inputArr) {

         

        if (inputArr == null || inputArr.length == 0) {

            return;

        }

        this.array = inputArr;

        length = inputArr.length;

        quickSort(0, length - 1);

    }

 

    private void quickSort(int lowerIndex, int higherIndex) {

         

        int i = lowerIndex;

        int j = higherIndex;

        // calculate pivot number, I am taking pivot as middle index number

        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];

        // Divide into two arrays

        while (i <= j) {

            /**

             * In each iteration, we will identify a number from left side which 

             * is greater then the pivot value, and also we will identify a number 

             * from right side which is less then the pivot value. Once the search 

             * is done, then we exchange both numbers.

             */

            while (array[i] < pivot) {

                i++;

            }

            while (array[j] > pivot) {

                j--;

            }

            if (i <= j) {

                exchangeNumbers(i, j);

                //move index to next position on both sides

                i++;

                j--;

            }

        }

        // call quickSort() method recursively

        if (lowerIndex < j)

            quickSort(lowerIndex, j);

        if (i < higherIndex)

            quickSort(i, higherIndex);

    }

 

    private void exchangeNumbers(int i, int j) {

        int temp = array[i];

        array[i] = array[j];

        array[j] = temp;

    }

     

    public static void main(String a[]){

         

        MyQuickSort sorter = new MyQuickSort();

        int[] input = {24,2,45,20,56,75,2,56,99,53,12};

        sorter.sort(input);

        for(int i:input){

            System.out.print(i);

            System.out.print(" ");

        }

    }

}