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:

- Pick an element that will serve as comparison point –
**pivot**. **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.- 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:

- See other
**sorting algorithms**in Algorithms Tutorial