* This WebWeekly presents a Quicksort algorithm you can use to quickly sort your arrays in ASP.
For the past six months or so, I've been reading and participating in a number of ASP ListServ groups. One question which arises often is how to sort an array efficiently. There are *many* sorting algorithms available, each having its own advantages and disadvantages.
The simplest sort, a bubble sort, is good for small arrays, especially ones that are nearly sorted already. However, as the set of data to be sorted starts to grow, a bubble sort becomes quite inefficient. The sort that is regarded as the best sort for large arrays that are NOT nearly sorted is Quicksort.
Quicksort uses a divide and conquer approach, dividing the total array in half, then recursively dividing each half info halves, and those halves into halves and so on and so on. Eventually, it just has two values, and can swap them if needed. While this is not exactly how a Quicksort works, it is a general description. What to remember is that a Quicksort uses a divide and conquer approach utilizing recursion. This leads to a big O of N log N.
I implemented this Quicksort algorithm using JavaScript. Since you can use JScript as a server-side language with ASP, its cut & paste time. You can also, as this code shows, use your Quicksort algorithm with client-side scripting as well. If you would like to see this algorithm coded in VBScript, let me know, and if there is enough interest, I will go ahead and provide a link to a VBScript implementation in the next WebWeekly.
An implementation of Quicksort in VBScript using one dimensional arrays can be at this URL. A VBScript implementation using two dimensional arrays can be found at this URL.
<SCRIPT LANGUAGE="JavaScript">
function Quicksort(vec, loBound, hiBound)
/**************************************************************
This function adapted from the algorithm given in:
Data Abstractions & Structures Using C++, by
Mark Headington and David Riley, pg. 586.
Quicksort is the fastest array sorting routine for
unordered arrays. Its big O is n log n.
**************************************************************/
{
var pivot, loSwap, hiSwap, temp;
// Two items to sort
if (hiBound - loBound == 1)
{
if (vec[loBound] > vec[hiBound])
{
temp = vec[loBound];
vec[loBound] = vec[hiBound];
vec[hiBound] = temp;
}
return;
}
// Three or more items to sort
pivot = vec[parseInt((loBound + hiBound) / 2)];
vec[parseInt((loBound + hiBound) / 2)] = vec[loBound];
vec[loBound] = pivot;
loSwap = loBound + 1;
hiSwap = hiBound;
do {
// Find the right loSwap
while (loSwap <= hiSwap && vec[loSwap] <= pivot)
loSwap++;
// Find the right hiSwap
while (vec[hiSwap] > pivot)
hiSwap--;
// Swap values if loSwap is less than hiSwap
if (loSwap < hiSwap)
{
temp = vec[loSwap];
vec[loSwap] = vec[hiSwap];
vec[hiSwap] = temp;
}
} while (loSwap < hiSwap);
vec[loBound] = vec[hiSwap];
vec[hiSwap] = pivot;
// Recursively call function... the beauty of quicksort
// 2 or more items in first section
if (loBound < hiSwap - 1)
Quicksort(vec, loBound, hiSwap - 1);
// 2 or more items in second section
if (hiSwap + 1 < hiBound)
Quicksort(vec, hiSwap + 1, hiBound);
}
function PrintArray(vec,lo,hi)
/**************************************************************
Simply print out an array from the lo bound to the
hi bound.
**************************************************************/
{
var i;
for (i = lo; i <= hi; i++)
document.write(vec[i] + "<BR>");
}
// Create an array and stuff some values in it
var x = new Array(10);
x[0] = 10;
x[1] = 1;
x[2] = 3;
x[3] = 8;
x[4] = 2;
x[5] = 11;
x[6] = 4;
x[7] = 22;
x[8] = 12;
x[9] = 6;
document.write("Here is a jumbled array:<BR>");
PrintArray(x,0,9);
Quicksort(x,0,9); // Sort the array using quicksort
document.write("<BR>Now the array is sorted!<BR>");
PrintArray(x,0,9);
</SCRIPT>
Happy Programming!
(WebWeekly is 100% free; email addresses are kept in strict confidence.)
