0

Quicksort is one of the fastest sorting algorithms. In this article we implement Quicksort in Java, describe how it works and its properties.

How Quicksort works

Similarly to merge sort, quicksort belongs to Divide and Conquer group of algorithms. It consists of the following steps:

  1. Pick an element that will serve as comparison point – pivot.
  2. Partition step – reorder elements in such a way that elements lower than pivot are on its left side and greater or equal to pivot are on its right side.
  3. Recursively sort subarrays on both sides of pivot element.

Contrary to merge sort, where real work was done in the merge step. In quicksort the real work is performed in partitioning step. And it is the partition function that differentiate implementations of quicksort.

The algorithm can be also parallelized, because it is a divide and conquer algorithm. But the pallalelization is worse than in case of merge sort, because the sizes of subarrays are sensitive to selection of pivot element.

Quicksort Pivot calculation strategies

  • pick the first/last element: easy to implement, but will downgrade performance, when the data is already sorted (why?)
  • pick an element from the middle
  • pick random element
  • calculate median of three (first, medium, and last): better performance in case of sorted data
  • calculate median of medians.

Quicksort properties

Quicksort has the following properties:

  • worst case performance is O(n^2) (selected pivot doesn’t split much)
  • average case performance is O(n log n)
  • worst case space complexity is O(n) or O(log n) (optimized version)
  • has many implementations (stable and unstable, in-place or not)

Quicksort implementation

In the following quicksort implementation we always use the last element of subarray as the pivot element: 

package com.farenda.tutorials.algorithms.sorting;

public class QuickSort {

    public void sort(int[] values) {
        sort(values, 0, values.length-1);
    }

    private void sort(int[] values, int first, int last) {
        if (first < last) {
            int pivot = partition(values, first, last);
            sort(values, first, pivot-1);
            sort(values, pivot+1, last);
        }
    }

    private int partition(int[] values, int first, int last) {
        int greater = first;
        for (int i = first; i < last; ++i) {
            if (values[i] <= values[last]) {
                swap(values, i, greater++);
            }
        }
        swap(values, greater, last);
        return greater;
    }

    private void swap(int[] values, int i, int j) {
        int tmp = values[i];
        values[i] = values[j];
        values[j] = tmp;
    }
}

As an exercise implement pivot selection using median-of-three strategy (calculate the median of the first, medium, and the last element). This strategy is more resilient to sorted data.

References:

Share with the World!