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.






[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.


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

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

[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.

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.

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.

 <title>Quicksort test</title>
  <script type="text/javascript" src="quicksort.js" >
 <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="" />

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.

function dosort(form)
	var array=form.unsorted.value.split(/ +/);


	form.sorted.value=array.join(' ');

Download code