Algorithm for finding two smallest numbers in an array

Problem Detail: 

I was just thinking today that the best approach to find two smallest numbers in any array would be to first sort(ascending order) it with some efficient algorithm like Quicksort(Average case complexity: nlogn) and then access the first two members of the array in O(1).

Is my approach optimal or there are some alternative better approaches?

Asked By : Rajat Saxena

Answered By : user2566092

If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 current smallest and if the new element is smaller, then you replace the larger of the 2 current smallest with the new element. This requires only a few operations per element in the array as you traverse the array, so it's $O(n)$ with a very small constant. It's probably impossible to come up with a sort-based approach that ever runs faster, except maybe for an array of size 4 or 5 or less.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47729