Array Sort UDFs from Akreutzer

 Keywords: ArraySort Array Sort

Here are three examples of UDF that will sort two-dimensional arrays.

SPEED

These routines were timed sorting a 5000x3 array...

ADOSort ... 7 Seconds
QSort ..... 24 Seconds
QSort2 .... 30 Seconds

ADOSort.wbt

Sorts using an ADODB.Recordset object. This is adapted from an example in the WinBatch Tech database, but that example had one drawback: it converted everything in the array to string data, regardless of what type it was before. The modified version does not change the data types.

;****************************************************************
;   Array sort using a recordset object.
;
;   ArraySort(Array,KeyColumn)
;
;       Array = The array to be sorted
;               It can be a 1 or two dimensional array.
;
;       KeyColumn = The column to be sorte, if the array is 2 dimensional.
;                   (Ignored for 1 dimensional arrays)
;
;   The return value is a new array containing the sorted values.
;   (The original array is not changed.)
;
;****************************************************************************
#DefineFunction ArraySort(Array,KeyColumn)
   TopRow = ArrInfo(Array,1)-1
   TopCol = ArrInfo(Array,2)-1
   ATitle = Arrayize("X.K",".")       ; Names for the columns
   AValue = ArrDimension(2)           ; Values for the columns

   RS=ObjectCreate("ADODB.RecordSet") ; Create recordset
   RS.fields.append("X",3)            ; 3 = Integer Type
   RS.fields.append("K",200,256)      ; 200 = String Type (202 = unicode)
   RS.Open
   For xRow=0 To TopRow
       AValue[0] = xRow
       AValue[1] = Array[xRow,KeyColumn]
       RS.addNew(ATitle,AValue)
   Next
   Drop(ATitle,AValue)

   NewArr = ArrDimension(TopRow+1,TopCol+1)
   RS.sort="K"
   RS.moveFirst
   For xRow=0 To TopRow
      xSort = Int(RS.Fields("X").value)
      For xCol=0 To TopCol
         NewArr[xRow,xCol] = Array[xSort,xCol]
      Next
      RS.moveNext
    Next
    RS.close
    RS=0
    Return NewArr
#EndFunction

QSort.wbt

Sort written using only WinBatch code. Sorts using the QuickSort algorithm. Note that one disadvantage of QuickSort is that it does not preserve the original order of data that has equal keys. Use this routine only if that doesn't matter.

;*************************************************************************
;
;   Array sort for two-dimensional arrays. Uses the "QuickSort" algorithm.
;
;   Array ....... The array to be sorted
;   KeyColumn ... The column to be used as the sort key
;
;   On return, the original array has been sorted.
;   (The actual return value is always zero, and may be ignored.)
;
;   NOTE that this sort method will not preserve the original
;   order of items with equal keys.
;
;**************************************************************************
#DefineFunction ArraySort(Array, KeyCol)
  TopRow = ArrInfo(Array,1)-1
  QuickSort(Array,KeyCol,0,TopRow)
  Return
#EndFunction

#DefineFunction QuickSort(Array, KeyColumn, LowBound, HighBound)
  If HighBound <= LowBound Then Return
  MaxColumn = ArrInfo(Array,2) -1

  xLow = LowBound
  xHigh = HighBound
  xPivot = Int((LowBound + HighBound) / 2)
  PivotValue = Array[xPivot,KeyColumn]

  While (xLow <= xHigh)
     While Array[xLow,KeyColumn] < PivotValue
          xLow = xLow + 1
          If xLow == HighBound Then Break
     EndWhile
     While PivotValue < Array[xHigh,KeyColumn]
          xHigh = xHigh - 1
          If xHigh == LowBound Then Break
     EndWhile
     If  xLow < xHigh
        For x = 0 To MaxColumn
           Temp = Array[xLow,x]
           Array[xLow,x] = Array[xHigh,x]
           Array[xHigh,x] = Temp
        Next
     EndIf
     If xLow <= xHigh
        xLow = xLow + 1
        xHigh = xHigh - 1
     End If
  EndWhile

  QuickSort(Array, KeyColumn, LowBound, xHigh)
  QuickSort(Array, KeyColumn, xLow, HighBound)
#EndFunction

QSort2.wbt

A modified QuickSort that will preserve the original order of equal keys.

;*************************************************************************
;
;   Array sort for two-dimensional arrays.
;
;   Uses the "QuickSort" algorithm, modified to
;   preserve the original row order for equal keys.
;
;   Array ....... The array to be sorted
;   KeyColumn ... The column to be used as the sort key
;
;   The return value is a copy of the original array, sorted.
;   (The original array is not modified.)
;
;**************************************************************************
#DefineFunction ArraySort(Array, KeyCol)
  TopRow = ArrInfo(Array,1)-1
  TopCol = ArrInfo(Array,2)-1
  KeyArr = ArrDimension(TopRow+1,2)
  For x = 0 To TopRow
       KeyArr[x,0] = Array[x,KeyCol]
       KeyArr[x,1] = x
  Next
  ArraySortKeys(KeyArr,0,TopRow)
  NewArr = ArrDimension(TopRow+1,TopCol+1)
  For x = 0 To TopRow
     R = KeyArr[x,1]
     For y = 0 To TopCol
         NewArr[x,y] = Array[R,y]
     Next
  Next
  Drop(KeyArr)
  Return NewArr
#EndFunction

;-----------------------------------------------------------
; Called recursively to sort the key array.
;   item[x,0] of the array is the sort key.
;   item[x,1] is the original row number, and is used
;             as a tie-breaker if the keys are equal.
;-----------------------------------------------------------
#DefineFunction ArraySortKeys(Array, LowBound, HighBound)
  If HighBound <= LowBound Then Return

  xLow = LowBound
  xHigh = HighBound
  xPivot = Int((LowBound + HighBound) / 2)
  PivotKey = Array[xPivot,0]
  PivotRow = Array[xPivot,1]

  While (xLow <= xHigh)
     While ArraySortArrayLess(xLow)
        xLow = xLow + 1
        If xLow == HighBound Then Break
     EndWhile
     While ArraySortPivotLess(xHigh)
         xHigh = xHigh - 1
         If xHigh == LowBound Then Break
     EndWhile
     If xLow < xHigh
         Temp = Array[xLow,0]
         Array[xLow,0] = Array[xHigh,0]
         Array[xHigh,0] = Temp
         Temp = Array[xLow,1]
         Array[xLow,1] = Array[xHigh,1]
         Array[xHigh,1] = Temp
     EndIf
     If xLow <= xHigh
         xLow = xLow + 1
         xHigh = xHigh - 1
     End If
  EndWhile

  ArraySortKeys(Array, LowBound, xHigh)
  ArraySortKeys(Array, xLow, HighBound)
#EndFunction

#DefineSubRoutine ArraySortArrayLess(xLess)
    If Array[xLess,0] < PivotKey Then Return @TRUE
    If Array[xLess,0] > PivotKey Then Return @FALSE
    Return Array[xLess,1] < PivotRow
#EndSubRoutine
#DefineSubRoutine ArraySortPivotLess(xLess)
    If PivotKey < Array[xLess,0] Then Return @TRUE
    If PivotKey > Array[xLess,0] Then Return @FALSE
    Return PivotRow < Array[xLess,1]
#EndSubRoutine

Article ID:   W16904

File Created: 2007:07:03:14:26:52

Last Updated: 2007:07:03:14:26:52

Database Search

TechHome