## More on finding the n smallest values of array

posted Tue 22 Jul 2014 by Michael Galloy under IDL, OptimizationAtle Borsholm recently posted a clever solution for finding the *n*-th smallest element in an array on the IDL Data Point. He compares this to a naive solution which simply sorts all the elements and grabs the *n*-th element:

```
IDL> tic & x = ordinal_1(a, 123456) & toc
% Time elapsed: 3.0336552 seconds.
```

His solution performs much better:

```
IDL> tic & x = ordinal_2(a, 123456) & toc
% Time elapsed: 0.46286297 seconds.
```

I have a `HISTOGRAM`

-based solution called `MG_N_SMALLEST`

in mglib that can do even better:

```
IDL> tic & x = mg_n_smallest(a, 123456) & toc
% Time elapsed: 0.18394303 seconds.
```

Note: `MG_N_SMALLEST`

does not return the *n*-th smallest element directly, but returns indices to the smallest `n`

elements.

I have a more detailed description of what `MG_N_SMALLEST`

is doing in an older article. I like this routine as a good example of using `HISTOGRAM`

and its `REVERSE_INDICES`

keyword. It also a nice example of when using a `FOR`

loop in IDL isn’t so bad.

I include even more detail on this routine in the “Performance” chapter of my book.

July 29th, 2014 at 9:05 am

Using a simple min() function might be even faster.

function ordinal_3,array,N

tmp = array

tmp1 = min(tmp,imin,max=tmp2)

ind = 0

tmp3 = tmp1

while (ind lt N) and (tmp3 lt tmp2) do begin

tmp[imin] = tmp2

tmp1 = min(tmp,imin)

if tmp1 gt tmp3 then begin

ind = ind+1

tmp3 = tmp1

endif

endwhile

return,tmp1

end

July 29th, 2014 at 9:14 am

Scrap my post. Only works for small N.