Difference between revisions of "Sorting and searching"
From Apache OpenOffice Wiki
(fix link) |
|||
Line 34: | Line 34: | ||
end sub | end sub | ||
</source> | </source> | ||
− | Based on a routine available from | + | Based on a routine available from [http://www.oopweb.com/Algorithms/Documents/Sman/Volume/ShellSort.html a Visual Basic version here]. |
Searching in a sorted list is compartively efficient with a binary search: | Searching in a sorted list is compartively efficient with a binary search: |
Revision as of 23:51, 2 March 2009
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