Using a random number to choose a pivot in quicksort

Pinterest LinkedIn Tumblr

Quicksort is an efficient comparison sorting algorithm. It can operate in place on an array, requiring small additional amounts of memory to perform sorting.

Quicksort can be faster than merge sort and heap sort. Quick sort is one of the divides and conquers strategy algorithm. It requires careful selection of pivot element. Even if the array nearly sorted or sorted the quicksort takes the same complexity. If the array nearly sorted, we can choose insertion sort for better complexity.

Write a program to implement the quicksort.

source Code

package com.dsacode.Algorithm.randomized;
import java.util.Arrays;
public class Quicksort {
      private int[] numbers;
      public Quicksort(int[] values) {
        if (values ==null ){
        this.numbers = values;
    public  void quicksort(int low, int high) {
        int l = low, h = high;
        int pivot = numbers[low + (high-low)/2];
        while (l <= h) {
          while (numbers[l] < pivot) {
          while (numbers[h] > pivot) {
          if (l <= h) {
            exchange(l, h);
        if (low < h)
          quicksort(low, h);
        if (l < high)
          quicksort(l, high);
      private  void exchange(int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    public static void main(String[] args) {
        int[] arr={12,34,56,23,45,78,46};
        System.out.println("unsorted array before sorting : " + Arrays.toString(arr));
        Quicksort q = new Quicksort(arr);
        q.quicksort(0, arr.length - 1);
        System.out.println("Sorted array After Quicksort sorting : " + Arrays.toString(arr));


Unsorted array before sorting: [12, 34, 56, 23, 45, 78, 46]
Sorted array After Quicksort sorting: [12, 23, 34, 45, 46, 56, 78]

Algorithm Explanation

Choose a pivot value from the array
Partition the array based on pivot element. Arrange all the elements less than pivot element to left side and greater elements to the right side of pivot element
Sort the left and right subarrays recursively
Merge the two solution subarrays.

Time Complexity

Best CaseAverage CaseWorst Case
O(n log n)O(n log n)O(n^2)


  1. http://en.wikipedia.org/wiki/Quicksort
  2. https://www.cs.auckland.ac.nz/software/AlgAnim/qsort.html
  3. http://me.dt.in.th/page/Quicksort/
  4. http://www.cs.armstrong.edu/liang/animation/web/QuickSortPartition.html

1 Comment

  1. Hi everybody, here every person is sharing such knowledge, thus it’s good to read this
    web site, and I used to pay a visit this webpage every day.

Write A Comment