Difference between revisions of "Sorting and searching"
From Apache OpenOffice Wiki
(remove from Category:Tutorials if in Category:Basic:Tutorials) |
|||
Line 3: | Line 3: | ||
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: | 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: | ||
− | < | + | <source lang="oobas"> |
sub subShellSort(mArray) | sub subShellSort(mArray) | ||
Line 33: | Line 33: | ||
loop | loop | ||
end sub | end sub | ||
− | </ | + | </source> |
Based on a routine available from [[http://www.oopweb.com/Algorithms/Documents/Sman/Volume/s_vss.txt here]]. | Based on a routine available from [[http://www.oopweb.com/Algorithms/Documents/Sman/Volume/s_vss.txt 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: | ||
− | < | + | <source lang="oobas"> |
function fnBinarySearch(a, v) | function fnBinarySearch(a, v) | ||
nLeft = 0 | nLeft = 0 | ||
Line 56: | Line 56: | ||
fnBinarySearch = -1 | fnBinarySearch = -1 | ||
end function | end function | ||
− | </ | + | </source> |
[[Category:Basic:Tutorials]] | [[Category:Basic:Tutorials]] |
Revision as of 17:49, 10 July 2008
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 [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