# Quicksort (JavaScript)

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

## 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>
<title>Quicksort test</title>
<script type="text/javascript" src="quicksort.js" >
</script>
<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(' ');
}
```