Sorting and searching

From Apache OpenOffice Wiki
Jump to: navigation, search

Neither OpenOffice.org Basic nor the API provide methods or functions for sorting arrays or searching within arrays.

It is quite common to sort almost sorted arrays, for example the list of style names belonging to a style family. Thus, I have found the shell sort to be the fastest for most uses in OpenOffice.org:

sub subShellSort(mArray)
 
dim n as integer, h as integer, i as integer, j as integer, t as string, Ub as integer, LB as integer
Lb = lBound(mArray)
Ub = uBound(mArray)
 
' compute largest increment
n = Ub - Lb + 1
h = 1
if n > 14 then
        do while h < n
                h = 3 * h + 1
        loop
        h = h \ 3
        h = h \ 3
end if
do while h > 0
' sort by insertion in increments of h
        for i = Lb + h to Ub
                t = mArray(i)
                for j = i - h to Lb step -h
                        if strComp(mArray(j), t, 0) < 1 then exit for
                        mArray(j + h) = mArray(j)
                next j
                mArray(j + h) = t
        next i
        h = h \ 3
loop
end sub

Based on a routine available from a Visual Basic version here.

Searching in a sorted list is compartively efficient with a binary search:

function fnBinarySearch(a, v)
nLeft = 0
nRight = uBound(a)
nLen = len(v)
while nLeft <= nRight
        nMid = int((nLeft + nRight)/2)
        if left(a(nMid), nLen) = v then
                fnBinarySearch = nMid
                exit function
        elseif v < a(nMid) then
                nRight = nMid - 1
        else
                nLeft = nMid + 1
        end if
wend
fnBinarySearch = -1
end function
Personal tools