QuickSort Performance Tests

OCTOBER 29, 2013

QuickSort is Fun, Sort Of

I am learning to work with algorithms. I am a little more interested in learning for the sake of mastery, rather than solving a specific problem. I am reading through TopCoder and also doing a little research on popular algorithm sites. QuickSort is supposedly the most consistently fast sorting algorithm. It averages better performance across tests when it is sorting a diverse set of unsorted lists.

QuickSort for Simple Value Lists

QuickSort uses a conquer and divide strategy, which works very well for simple value lists: because the cost of comparing two values is small. This strategy is useful when attempting to settle as many comparisons as it can without repeating them. By comparing each number in a set and dividing the set into two sets, it is minimizing the number of times a number will be compared with the whole set. Discarding the pivot from further comparisons also increases the efficiency slightly. QuickSort is efficient because it is comparing each numbers to another number Log(N) times [Where N is the number of items in the list]. Comparing it to BubbleSort which compares each number N times. BubbleSort will require N*N comparisons per number, while QuickSort will require N * Log(N) comparison operations per number, and so we derive a Big O notation with an efficiency of O(N Log N) which is better than N squared.

A comparison of algorithmic efficiency. Where Square(N) is representative of algorithms like Bubble Sort, and N*Log(N) is representative of  QuickSort, and MergeSort. However, this graph shows the theoretical limit of efficiency. not the actual efficiency.

A comparison of algorithmic efficiency. Where Square(N) is representative of algorithms like Bubble Sort, and N*Log(N) is representative of QuickSort, and MergeSort. However, this graph shows the theoretical limit of efficiency. not the actual efficiency.

As the cost of comparing values increases, QuickSort becomes less efficient. The efficiency of QuickSort can be expressed as O(N * Log N), with N being the number of items to compare, but that does not consider the cost of comparison. QuickSort tackles a simple problem of (are a given set of values less than or greater than a chosen value).

QuickSort does not tackle the problem of putting values in order; but that problem is being solved as a corollary to the simpler problem of divide and conquer. If QuickSort continues to recursively do it's job, then it will effectively sort the values in the list into an ordered list.

For a really cool comparison of some popular sorting algorithms checkout http://www.sorting-algorithms.com/ , showing real time performance comparisons of several.

Without Further Ado: Here is my QuickSort

function QuickSort(numbers) {
  var index = Math.floor(numbers.length / 2);
  var pivot = numbers[index];
  var left = [];
  var right = [];
  for (i in numbers) {
    var num = numbers[i];
    if (num < pivot) {
      left.push(num);
    }
    if (num > pivot) {
      right.push(num);
    }
  }
  if (left.length > 1) {
    left = QuickSort(left);
  }
  if (right.length > 1) {
    right = QuickSort(right);
  }
  return left.concat([pivot], right);
}

Results of My Work Tonight

Check out how my implementation compares with another implementation I found on RosettaCode (Functional QuickSort).

Comparing (jsPerf) QuickSort(random) versus QuickSort(half) versus QuickSort(functional), and native .sort method.

Here is a jsFiddle proving they all work in doing the sort.

In my testing, implementing my own QuickSort in Javascript is much slow than the native sort methods (which use the V8 engine directly).