Difference between revisions of "Sorting and searching"
From Apache OpenOffice Wiki
m |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | Neither | + | Neither {{AOo}} 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 | + | 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 {{AOo}}: |
| − | < | + | <syntaxhighlight lang="oobas"> |
sub subShellSort(mArray) | sub subShellSort(mArray) | ||
| Line 33: | Line 33: | ||
loop | loop | ||
end sub | end sub | ||
| − | </ | + | </syntaxhighlight> |
| − | + | ||
| − | Searching in a sorted list is | + | Searching in a sorted list is comparatively efficient with a binary search: |
| − | < | + | <syntaxhighlight lang="oobas"> |
function fnBinarySearch(a, v) | function fnBinarySearch(a, v) | ||
nLeft = 0 | nLeft = 0 | ||
| Line 56: | Line 55: | ||
fnBinarySearch = -1 | fnBinarySearch = -1 | ||
end function | end function | ||
| − | </ | + | </syntaxhighlight> |
[[Category:Basic:Tutorials]] | [[Category:Basic:Tutorials]] | ||
Latest revision as of 12:38, 4 February 2021
Neither Apache OpenOffice 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 Apache OpenOffice:
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
Searching in a sorted list is comparatively 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
