Difference between revisions of "Sorting and searching"

From Apache OpenOffice Wiki
Jump to: navigation, search
 
Line 57: Line 57:
 
end function
 
end function
 
</code>
 
</code>
 +
 +
[[Category:Basic:Tutorials]]
 +
[[Category:Tutorials]]

Revision as of 17:41, 16 May 2006

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:

[oobas] 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 [here].

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

[oobas] 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