Quicksort (JavaScript)

From LiteratePrograms
Jump to: navigation, search
Other implementations: AWK | C | C++ | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Oz | Python | Python, arrays | Sed | Visual Basic .NET

An implementation of quick sort in Javascript.

<<quicksort.js>>=
partition

qsort

quick_sort

testing

Contents

[edit] Overview

Quick sort works like this:

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

[edit] Partition

The partition function moves all elements that are less than the pivot value to the beginnig of the 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;
}

[edit] Quick sort

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);
}

[edit] Testing

To test our code, we create a simple web page, containing 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
hijacker
hijacker
hijacker
hijacker