; docformat = 'rst'
;+
; Finds the n smallest elements of a data array. This algorithm works fastest on
; uniformly distributed data. The worst case for it is a single smallest data
; element and all other elements with another value. This will be nearly
; equivalent to just sorting all the elements and choosing the first n elements.
;
; :Returns:
; index array
;
; :Params:
; data : in, required, type=numeric array
; data array of any numeric type (except complex/dcomplex)
; n : in, required, type=integer
; number of smallest elements to find
;
; :Keywords:
; largest : in, optional, type=boolean
; set to find n largest elements
;-
function mg_n_smallest, data, n, largest=largest
compile_opt strictarr
on_error, 2
; both parameters are required
if (n_params() ne 2) then begin
message, 'required parameters are missing'
endif
; use histogram to find a set with more elements than n of smallest elements
nData = n_elements(data)
nBins = nData / n
h = histogram(data, nbins=nBins, reverse_indices=ri)
; set parameters based on whether finding smallest or largest elements
if (keyword_set(largest)) then begin
startBin = nBins - 1L
endBin = 0L
inc = -1L
endif else begin
startBin = 0L
endBin = nBins - 1L
inc = 1L
endelse
; loop through the bins until we have n or more elements
nCandidates = 0L
for bin = startBin, endBin, inc do begin
nCandidates += h[bin]
if (nCandidates ge n) then break
endfor
; get the candidates and sort them
candidates = keyword_set(largest) ? $
ri[ri[bin] : ri[nBins] - 1L] : $
ri[ri[0] : ri[bin + 1L] - 1L]
sortedCandidates = sort(data[candidates])
if (keyword_set(largest)) then sortedCandidates = reverse(sortedCandidates)
; return the proper n of them
return, (candidates[sortedCandidates])[0:n-1L]
end