Arrays.sort or iterative search?
I have a large integer array of mixed values I want to search for the highest and lowest values. I have a method to iterate through each element in the array. I was thinking Arrays.sort() might be faster, however I need to retain the order of the elements in the array.
Would it be more efficient to:
a) Stick with the iterative method
b) Make a copy of the array, sort and then take the first and last elements and lowest and highest respectively
Any suggestions much appreciated
Re: Arrays.sort or iterative search?
Have you heard of the QuickSelect algorithm? It's quite good at finding the min/max (I think in practice it's about O(log(n)) average, O(n) worst case).
If you only need a few min/max value, I'd say stick with the quickselect algorithm. Otherwise, it may just be better to use the full quicksort routine (which is probably the algorithm used by Array.sort()).
I was mistaken. The best way to find the #1 min/max is to iterate. The best way to find the #nth min/max is to use quickselect, or quicksort if you need to find a lot of min/max values.