Quicksort with 3-way partition

algorithm quicksort
CodeMonkey1313 picture CodeMonkey1313 · Jun 2, 2009 · Viewed 45.4k times · Source

What is QuickSort with a 3-way partition?

Answer

jjnguy picture jjnguy · Jun 2, 2009

Picture an array:

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0

A two partition Quick Sort would pick a value, say 4, and put every element greater than 4 on one side of the array and every element less than 4 on the other side. Like so:

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5

A three partition Quick Sort would pick two values to partition on and split the array up that way. Lets choose 4 and 7:

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9

It is just a slight variation on the regular quick sort.

You continue partitioning each partition until the array is sorted. The runtime is technically nlog3(n) which varies ever so slightly from regular quicksort's nlog2(n).

Related questions

Quicksort with Python

I am totally new to python and I am trying to implement quicksort in it. Could someone please help me complete my code? I do not know how to concatenate the three arrays and printing them. def sort(array=[12,4,5,6,7,3,1,15]): less = [] …

Read More
Why is quicksort better than mergesort?

I was asked this question during an interview. They're both O(nlogn) and yet most people use Quicksort instead of Mergesort. Why is that?

Read More
Quicksort: Choosing the pivot

When implementing Quicksort, one of the things you have to do is to choose a pivot. But when I look at pseudocode like the one below, it is not clear how I should choose the pivot. First element of list? …

Read More