Quicksort

 

Overview

Originally developed in 1960 by Tony Hoare while studying at Moscow State University, Quicksort has become one the most important sorting algorithms to master. In essence, quicksort is a divide and conquer algorithm which divides an array (or list) to be sorted into two smaller sub-arrays (or lists) and recursively sorts each.

Concept

The basic steps of Quicksort include:

  1. Pick a given element from the initial array (or list), which will be called the pivot.
  2. Arrange the array so that all the elements with values less than the pivot come before the pivot and all values greater than the pivot come after it.
  3. Recursively apply steps 1 – 2 to the elements of each of the sub-arrays.

Algorithmic Complexity

In practice Quicksort behaves faster than other O(n * log (n)) algorithms, which is one of the main reasons why it is so commonly used.  Its worst case Big-O time complexity is O(n^2), however this behavior is considered extremely rare. In the best and average case, the Big-O time complexity of Quicksort is O(n * log (n)). The worst case space complexity of Quicksort is O(n) auxiliary space, however it can be implemented to only use O(log n) auxiliary space.

Big-O

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
QuicksortArrayO(n log(n))O(n log(n))O(n^2)O(n)

Implementation

Java Implementation


import java.util.ArrayList;
import java.util.List;

/**
 * Quicksort algorithm implementation
 *
 * www.algorithmiccomplexity.com
 */
public class Quicksort {
	
	public static List quicksort(List unsortedList)
	{
		int size = unsortedList.size();
		
		if(size < 2)
		{
			return unsortedList;
		}
		
		Integer pivot = unsortedList.get(0);
		
		List less = new ArrayList<>();
		List equal = new ArrayList<>();
		List greater = new ArrayList<>();
		
		for(Integer element : unsortedList)
		{
			if(element < pivot)
			{
				less.add(element);
			}
			else if(element == pivot)
			{
				equal.add(element);
			}
			else
			{
				greater.add(element);
			}	
		}
		
		less = quicksort(less);
		greater = quicksort(greater);
		
		List result = new ArrayList<>();
		
		for(Integer element : less)
		{
			result.add(element);
		}
		for(Integer element : equal)
		{
			result.add(element);
		}
		for(Integer element : greater)
		{
			result.add(element);
		}
		
		return result;
		
	}
	
	/**
	 * Test driver for the quicksort algorithm.
	 * 
	 * @param args Command line arguments {@code null}.
	 */
	public static void main(String[] args)
	{
		List unsortedList = new ArrayList<>();
		unsortedList.add(10);
		unsortedList.add(5);
		unsortedList.add(3);
		unsortedList.add(7);
		unsortedList.add(1);
		unsortedList.add(8);
		unsortedList.add(8);
		unsortedList.add(0);
		unsortedList.add(6);
		
		System.out.println(unsortedList);
		unsortedList = Quicksort.quicksort(unsortedList);
		System.out.println(unsortedList);
	}
} 

References

Wikipedia: Quicksort

 

<- back