QuickSort in Action - Code for Quicksort
(Page 5 of 6 )
I used JavaScript and a blank HTML page to implement the algorithm. The onload event of the HTML page calls the Quicksort function. This is the code:
<html>
<head>
<script type="text/javascript">
//the array and elements to sort
theList = new Array()
theList[0] = 'Q';
theList[1] = 'W';
theList[2] = 'E';
theList[3] = 'R';
theList[4] = 'T';
theList[5] = 'Y';
theList[6] = 'U';
theList[7] = 'I';
theList[8] = 'O';
theList[9] = 'P';
//function to swap two array elements
function swap(m,n)
{
var temp = theList[m];
theList[m] = theList[n];
theList[n] = temp;
}
//the Quicksort function
function quickSort(arr,left,right)
{//the function receives an array (arr) and indices for the left and right elements
i = left;
j = right;
if(arr[i] > arr[j])
{
swap(i, j);
}
do //increment i and decrement j, then swap if necessary
{
do
{
if ((i+1)<=right) //do not increment i beyond the index for the right element
{
++i;
}
} while (arr[i] < arr[left])
do
{
if ((j-1)>=left) //do not decrement j beyond the index for the left element
{
--j;
}
} while (arr[j] > arr[left])
if (i<j)
{
swap(i, j);
}
} while (i < j)
swap(j, left);
var k = j; //the pivot.
var leftLeft = left; //the index for the left element of the left sub-list, initialized
if ((k-1)>=left) //we do not want a value for k that will be less than the left index
{
var leftRight = k - 1; //the index for the right element of the left sub-list, initialized
}
if ((k+1)<=right) //we do not want a value for k that will be greater than the right index
{
var rightLeft = k + 1; //the index for the left element of the right sub-list, initialized
}
var rightRight = right; //the index for the right element of the right sub-list, initialized
//recursion for the left sub-list - only called if a left sub-list exists
if (k != left)
{
quickSort(arr,leftLeft,leftRight);
}
//recursion for the right sub-list - only called if a right sub-list exists
if (k != right)
{
quickSort(arr,rightLeft,rightRight);
}
}
function sort()
{
var left = 0;
var right = theList.length - 1;
quickSort(theList,left,right);
alert(theList.join()); //display result in a message box
}
</script>
</head>
<body onload="sort()">
</body>
</html>
Next: Sorting Strings >>
More JavaScript Articles
More By Chrysanthus Forcha
/ 3 
