When you think ASP, think...
Recent Articles
All Articles
ASP.NET Articles
ASPFAQs.com
Message Board
Related Web Technologies
User Tips!
Coding Tips

Sections:
Sample Chapters
Commonly Asked Message Board Questions
JavaScript Tutorials
MSDN Communities Hub
Official Docs
Security
Stump the SQL Guru!
XML Info
Information:
Feedback
Author an Article
ASP ASP.NET ASP FAQs Message Board Feedback
Print this page.
Published: Wednesday, January 27, 1999

Sorting Two Dimensional Arrays: VBScript Implementation


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.

- continued -

'

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 VBScript. Since you can use VBScript 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 (although if you choose to use client side scripting, I would highly recommend a JavaScript implementation, which can be found here).

An implementation of Quicksort in JavaScript can be found via this URL. An algorithm to sort a one dimensional array can be found at this URL.


<%@ Language="VBScript" %>
<%

Option Explicit

'==-----------------------------------------------------------==
'== 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.       ==
'==                                                           ==
'== This version sorts 2-dimensional arrays on a single field ==
'==-----------------------------------------------------------==

Response.Write "<HTML><HEAD></HEAD><BODY BGCOLOR=""WHITE"">"


Sub SwapRows(ary,row1,row2)
  '== This proc swaps two rows of an array 
  Dim x,tempvar
  For x = 0 to Ubound(ary,2)
    tempvar = ary(row1,x)    
    ary(row1,x) = ary(row2,x)
    ary(row2,x) = tempvar
  Next
End Sub  'SwapRows

Sub QuickSort(vec,loBound,hiBound,SortField)

  '==--------------------------------------------------------==
  '== Sort a 2 dimensional array on SortField                ==
  '==                                                        ==
  '== 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               ==
  '==                                                        ==
  '== Parameters:                                            ==
  '== vec       - array to be sorted                         ==
  '== SortField - The field to sort on (2nd dimension value) ==
  '== loBound and hiBound are simply the upper and lower     ==
  '==   bounds of the array's 1st dimension.  It's probably  ==
  '==   easiest to use the LBound and UBound functions to    ==
  '==   set these.                                           ==
  '==--------------------------------------------------------==

  Dim pivot(),loSwap,hiSwap,temp,counter
  Redim pivot (Ubound(vec,2))

  '== Two items to sort
  if hiBound - loBound = 1 then
    if vec(loBound,SortField) > vec(hiBound,SortField) then Call SwapRows(vec,hiBound,loBound)
  End If

  '== Three or more items to sort
  
  For counter = 0 to Ubound(vec,2)
    pivot(counter) = vec(int((loBound + hiBound) / 2),counter)
    vec(int((loBound + hiBound) / 2),counter) = vec(loBound,counter)
    vec(loBound,counter) = pivot(counter)
  Next

  loSwap = loBound + 1
  hiSwap = hiBound
  
  do
    '== Find the right loSwap
    while loSwap < hiSwap and vec(loSwap,SortField) <= pivot(SortField)
      loSwap = loSwap + 1
    wend
    '== Find the right hiSwap
    while vec(hiSwap,SortField) > pivot(SortField)
      hiSwap = hiSwap - 1
    wend
    '== Swap values if loSwap is less then hiSwap
    if loSwap < hiSwap then Call SwapRows(vec,loSwap,hiSwap)


  loop while loSwap < hiSwap
  
  For counter = 0 to Ubound(vec,2)
    vec(loBound,counter) = vec(hiSwap,counter)
    vec(hiSwap,counter) = pivot(counter)
  Next
    
  '== 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,SortField)
    '== 2 or more items in second section
    if hiSwap + 1 < hibound then Call QuickSort(vec,hiSwap+1,hiBound,SortField)

End Sub  'QuickSort

Sub PrintArray(vec,lo,hi,mark)
  '==-----------------------------------------==
  '== Print out an array from the lo bound    ==
  '==  to the hi bound.  Highlight the column ==
  '==  whose number matches parm mark         ==
  '==-----------------------------------------==

  Dim i,j
  Response.Write "<table border=""1"" cellspacing=""0"">"
  For i = lo to hi
    Response.Write "<tr>"
    For j = 0 to Ubound(vec,2)
      If j = mark then 
        Response.Write "<td bgcolor=""FFFFCC"">"
      Else 
        Response.Write "<td>"
      End If
      Response.Write vec(i,j) & "</td>"
    Next
    Response.Write "</tr>"
  Next
  Response.Write "</table>"
End Sub  'PrintArray



Randomize

Dim x(9,5),z,y
Const col = 0


For z = 0 to 9
  For y = 0 to 5
    x(z,y) = int(Rnd*1000)
    If (Rnd < 0.5) then x(z,y) = x(z,y)-1000
  Next
Next


Response.Write "Here is a jumbled array:<BR>"
Call PrintArray(x,0,9,col)

Call QuickSort(x,0,9,col)

Response.Write "<BR>Now the array is sorted!<BR>"
Call PrintArray(x,0,9,col)

Response.Write "</BODY></HTML>"
%>

Happy Programming!

Related Articles
  • Quicksort for One Dimensional Arrays: VBScript Implementation
  • Quicksort for Two Dimensional Arrays: VBScript Implementation
  • Quicksort for One Dimensional Arrays: JavaScript Implementation
  •  


    Kevin Moon is an accomplished ASP developer, who translated the Quicksort algorithm from JavaScript to VBScript, and also coded a two dimensional version of Quicksort.



    ASP.NET [1.x] [2.0] | ASPMessageboard.com | ASPFAQs.com | Advertise | Feedback | Author an Article