Quicksort (JavaScript)

From LiteratePrograms

Jump to: navigation, search
Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc

A Javascript implementation of quick sort for arrays. This implementation uses a random pivot value to ensure that the performance of the sort is, with high probability, not compromised by pathological input arrays (such as an already-sorted array).

Contents

Implementation

The basic quicksort algorithm consists of the following steps:

  • Select a pivot value in the array
  • Move all elements smaller than the pivot to the beginning of the array
  • Repeat recursively for both smaller and bigger values

Partitioning

The partitioning function scans an array segment array from element begin to element end, and moves all elements that are less than the pivot value to the beginning of array. 

<<partition>>=
swap
function partition(array, begin, end, pivot)
{
	var piv=array[pivot];
	array.swap(pivot, end-1);
	var store=begin;
	var ix;
	for(ix=begin; ix<end-1; ++ix) {
		if(array[ix]<=piv) {
			array.swap(store, ix);
			++store;
		}
	}
	array.swap(end-1, store);
	return store;
}

In partition(), we used the swap() method of Array. This is not included in standard Javascript, so we have to define it. 

<<swap>>=
Array.prototype.swap=function(a, b)
{
	var tmp=this[a];
	this[a]=this[b];
	this[b]=tmp;
}

Quicksort

The qsort() function takes an array, a start index and an end index (pointing 1 element past the last element to be sorted). This implementation uses a random pivot value. 

<<qsort>>=
function qsort(array, begin, end)
{
	if(end-1>begin) {
		var pivot=begin+Math.floor(Math.random()*(end-begin));
		pivot=partition(array, begin, end, pivot);
		qsort(array, begin, pivot);
		qsort(array, pivot+1, end);
	}
}

Normally, a user wants to sort a complete array, so we provide a convenience function where it is not necessary to specify the indexes. 

<<quick_sort>>=
function quick_sort(array)
{
	qsort(array, 0, array.length);
}

Testing

The complete quicksort.js Javascript source file includes the functions that make up the quicksort implementation, as well as some support functions for testing: 

<<quicksort.js>>=
partition
qsort
quick_sort
testing

To test our code, we create a simple web page that makes use of quicksort.js. The web page contains a text box with unsorted items, and another where the result of quick_sort() is stored. We also include a button with the onclick handler pointing to the dosort() helper function. 

<<quicksort.html>>=
<html>
<head>
 <title>Quicksort test</title>
  <script type="text/javascript" src="quicksort.js" >
  </script>
</head>
<body>
 <form id="qsform" action="" method="" >
  <input type="text" size="80" name="unsorted" 
   value="Paris London Stockholm Berlin Oslo Rome Madrid Tallinn Amsterdam Dublin" /> <br />
  <input type="button" name="sort" value="Sort" onclick="dosort(this.form)" /> <br />
  <input type="text" size="80" name="sorted" value="" />
 </form>
</body>
</html>

dosort() is a helper function, translating the unsorted text into an array, calling quick_sort(), translating the sorted array back to a string and write it to the sorted text box. 

<<testing>>=
function dosort(form)
{
	var array=form.unsorted.value.split(/ +/);
	quick_sort(array);
	form.sorted.value=array.join(' ');
}
Download code
Retrieved from "http://literateprograms.org/Quicksort_%28JavaScript%29"
Views