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.
<%@ Language="VBScript" %>
'== This entire piece of code was shamelessly stolen from
'== the 4 Guys From Rolla WebWeekly newsletter, translated
'== to VBScript and changed into server-side ASP code.
'== Every effort has been made to keep comments intact.
Response.Write "<HTML><HEAD></HEAD><BODY BGCOLOR=""WHITE"">"
'== This procedure is 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
'== Two items to sort
if hiBound - loBound = 1 then
if vec(loBound) > vec(hiBound) then
vec(loBound) = vec(hiBound)
vec(hiBound) = temp
'== Three or more items to sort
pivot = vec(int((loBound + hiBound) / 2))
vec(int((loBound + hiBound) / 2)) = vec(loBound)
vec(loBound) = pivot
loSwap = loBound + 1
hiSwap = hiBound
'== Find the right loSwap
while loSwap < hiSwap and vec(loSwap) <= pivot
loSwap = loSwap + 1
'== Find the right hiSwap
while vec(hiSwap) > pivot
hiSwap = hiSwap - 1
'== Swap values if loSwap is less then hiSwap
if loSwap < hiSwap then
temp = vec(loSwap)
vec(loSwap) = vec(hiSwap)
vec(hiSwap) = temp
loop 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) then Call QuickSort(vec,loBound,hiSwap-1)
'== 2 or more items in second section
if hiSwap + 1 < hibound then Call QuickSort(vec,hiSwap+1,hiBound)
End Sub 'QuickSort
'== Simply print out an array from the lo bound to the hi bound.
For i = lo to hi
Response.Write vec(i) & "<BR>"
End Sub 'PrintArray
For z = 0 to 9
x(z) = int(Rnd*1000)
If (Rnd < 0.5) then x(z) = x(z)-1000
Response.Write "Here is a jumbled array:<BR>"
Now the array is sorted!</BR>" Call PrintArray(x,0,9) Response.Write "</BODY></HTML>" %>