Click here to Skip to main content
15,868,048 members
Articles / Desktop Programming / MFC

Computer Algorithms: Quicksort

Rate me:
Please Sign up or sign in to vote.
5.00/5 (2 votes)
25 Mar 2012CPOL4 min read 40.5K   6   5
Quicksort is a very elegant general purpose sorting algorithm and every developer should be familiar with its principles.

Introduction

When it comes to sorting items by comparing them, merge sort is one very natural approach. It is natural, because it simply divides the list into two equal sub-lists, then sort these two partitions applying the same rule. That is a typical divide and conquer algorithm and it just follows the intuitive approach of speeding up the sorting process by reducing the number of comparisons. However, there are other “divide and conquer” sorting algorithms that do not follow the merge sort scheme, while they have practically the same success. Such an algorithm is quicksort.

Overview

Back in 1960, C. A. R. Hoare came up with a brilliant sorting algorithm. In general, quicksort consists of some very simple steps. First, we’ve to choose an element from the list (called a pivot), then we must put all the elements with value less than the pivot on the left side of the pivot and all the items with value greater than the pivot on its right side. After that, we must repeat these steps for the left and the right sub-lists. That is quicksort! Simple and elegant!

Quicksort

It is a pure divide and conquer approach as merge sort, but while merge sort’s tricky part was merging the sorted sub-lists, in quicksort, there are other things to consider.

First of all, obviously the choice of a pivot is the bottleneck. Indeed, it all depends on that pivot. Imagine that you choose the greatest value from the list – then you’ve to put all the other items of the list into the “left” sub-list. If you do that on each step, you’ll practically go into the worst scenario and that is no good. The thing is that in the worst case, quicksort is not so effective and it’s practically as slow as bubble sort and insertion sort. The good thing is that in practice with randomly generated lists, there is not a high possibility to go into the worst case of quicksort.

Choosing a Pivot

Of course, the best pivot is the middle element from the list. Thus, the list will be divided into two fairly equal sub-lists. The problem is that there’s not an easy way to get the middle element from a list and this will slow down the algorithm. So typically, we can get for a pivot the first or the last item of the list.

After choosing a pivot, the rest is simple. Put every item with a greater value on the right and every item with a lesser value on the left. Then, we must sort the left and right sub-lists just as we did with the initial list.

Merging in Quicksort

It’s clear that with this algorithm naturally we’re going into a recursive solution. Typically, every divide and conquer approach is easy to implement with recursion. But because recursion can be heavy, there is an iterative approach.

Implementation

As I said above, recursive approach is something very natural for quicksort as it follows the divide and conquer principles. On each step, we divide the list in two and we pass those sub-lists to our recursive function. But recursion is dangerous sometimes, so an iterative approach is also available. Typically, iterative approaches “model” recursion with extra memory and a model of a stack, which is our case. Here, we have two examples of quicksort – recursive and iterative in PHP. Let’s go first with the recursion.

Recursive Quicksort

PHP
$list = array(5,3,9,8,7,2,4,1,6,5);
 
// recursive
function quicksort($array)
{
	if (count($array) == 0) {
    	return array();
	}
 
	$pivot = $array[0];
	$left = $right = array();
 
	for ($i = 1; $i < count($array); $i++) {
		if ($array[$i] < $pivot) {
			$left[] = $array[$i];
		} else {
			$right[] = $array[$i];
		}
	}
 
	return array_merge(quicksort($left), array($pivot), quicksort($right));
}
 
// 1, 2, 3, 4, 5, 5, 6, 7, 8, 9
print_r(quicksort($list));

Iterative Quicksort

PHP
$list = array(5,3,9,8,7,2,4,1,6,5);
 
// iterative
function quicksort_iterative($array)
{
    $stack = array($array);
    $sorted = array();
 
    while (count($stack) > 0) {
 
        $temp = array_pop($stack);
 
        if (count($temp) == 1) {
            $sorted[] = $temp[0];
            continue;
        }
 
        $pivot = $temp[0];
        $left = $right = array();
 
        for ($i = 1; $i < count($temp); $i++) {
            if ($pivot > $temp[$i]) {
                $left[] = $temp[$i];
            } else {
                $right[] = $temp[$i];
            }
        }
 
        $left[] = $pivot;
 
        if (count($right))
            array_push($stack, $right);
        if (count($left))
            array_push($stack, $left);
    }
 
    return $sorted;
}
 
// 1, 2, 3, 4, 5, 5, 6, 7, 8, 9
print_r(quicksort_iterative($list));

Complexity

The complexity of quicksort in the average case is O(n*log(n)) – same as Merge sort. The problem is that in the worst case it is O(n2) – same as bubble sort. Obviously, the worst case is when we have an already sorted list, and we constantly take for a pivot the last element of the list. But we should consider that in practice we don’t quite use sorted lists that we have to sort again, right?

Quicksort average and worst case scenarios

Application

Quicksort is a great sorting algorithm and developers often go for it, but let’s see some pros and cons of it.

Why Using Quicksort

  1. Recursive implementation is easy
  2. In general, its speed is the same as merge sort – O(n*log(n))
  3. Elegant solution with no tricky merging as merge sort

Why Not Using Quicksort

  1. As slow as bubble sort in the worst case!
  2. Iterative implementation isn’t easy
  3. There are faster algorithms for some sets of data types

Quicksort is beautiful because of the elegant idea behind its principles. Indeed if you have two sorted lists, one with items with a greater value from a given value and the other with items smaller form that given value, you can simply concatenate them and you can be sure that the resulting list will be sorted with no need of special merge.

In fact, quicksort is a very elegant general purpose sorting algorithm and every developer should be familiar with its principles.

Related Posts

  1. Friday Algorithms: Quicksort – Difference Between PHP and JavaScript
  2. Computer Algorithms: Merge Sort
  3. Computer Algorithms: Radix Sort

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Bulgaria Bulgaria
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralSimple and Clear Pin
karthik cad/cam27-Mar-13 0:08
karthik cad/cam27-Mar-13 0:08 
Question$ before these vars Pin
tony vo manh cuong29-Aug-12 3:15
tony vo manh cuong29-Aug-12 3:15 
GeneralMy vote of 5 Pin
dex.ilic27-Mar-12 23:08
dex.ilic27-Mar-12 23:08 
QuestionComputer Algorithms: Quicksort Pin
Millymanz26-Mar-12 23:18
Millymanz26-Mar-12 23:18 
QuestionXml code needs formatting Pin
Abhinav S24-Mar-12 16:53
Abhinav S24-Mar-12 16:53 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.