4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Best regarding what? Given an environment that provides an O(nlogn) time sort, but no competent quickselect, I'd go for sort. $\endgroup$ – greybeard Sep 30 '15 at 19:49
  • $\begingroup$ Why in the world would you need to sort an array to find smallest numbers? This is trivially done with a single pass. $\endgroup$ – Davor Oct 1 '15 at 13:17
  • $\begingroup$ This problem is studied at length in Knuth's TAoCP (Vol 3, iirc). $\endgroup$ – Raphael Apr 12 '16 at 9:24
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I initially thought that as a solution. So,I guess my brute-force technique was right. $\endgroup$ – Rajat Saxena Oct 6 '15 at 7:59
  • $\begingroup$ This method uses $2n$ comparisons in the worst case, while it is possible with $1.5n$ comparisons in the worst case. Group the elements into pairs, and compute the smallest and largest of each pair. Then apply the method in this answer to compute the smallest and second smallest of all the "smallest" elements. The actual second smallest is the minimum of the second smallest found and the larger element in the pair from which the smallest element came. $\endgroup$ – Tom van der Zanden Jan 9 '16 at 15:57
6
$\begingroup$

The optimal number of comparisons (not necessarily the fastest one) goes like this for $n = 2^k$:

  1. Compare $a_1$ and $a_2$, $a_3$ and $a_4$, and so on. Store only the smallest of each pair in a list $b_1,\ldots,b_{n/2}$.

  2. Repeat $k-1$ more times to get the minimum $a_{\min}$.

  3. Let $L$ be the set of all $k$ elements which were compared to $a_{\min}$ and were larger. Find the minimum of $L$. This is the second minimal element.

This algorithm uses $n + \log_2 n - 2$ comparisons, which is the optimal number of comparisons. However, implementing the logic isn't trivial, so in practice it might be slower than the algorithm in user2566092's answer.

$\endgroup$
  • $\begingroup$ At step 2 you have used $n-1$ compares. The smallest element has been compared to $k$ others, so we need $k-1$ compares. The total is then $n+k-2$, I believe. $\endgroup$ – Ross Millikan Sep 30 '15 at 22:25
4
$\begingroup$

No, it's not optimal. Do you know an efficient way of finding the smallest number in an array? Knowing the smallest number, could you adapt that method to find the second smallest?

$\endgroup$
3
$\begingroup$

Hoare's algorithm, which Wikipedia calls Quickselect, can find the $k$ smallest elements of an array in $O(n)$ time for any fixed $k$.

It is a modified Quicksort algorithm that sorts the array but stops early, leaving the beginning part correct (in this case the first two elements) and the rest of the array in whatever partly-sorted state is most convenient.

$\endgroup$
  • 4
    $\begingroup$ For "find the two smallest" this is surely way overkill. $\endgroup$ – vonbrand Sep 30 '15 at 15:48
  • $\begingroup$ I agree, for "find the two smallest" it is overkill. $\endgroup$ – Mark Dominus Sep 30 '15 at 16:21
  • $\begingroup$ If the question is to find the two numbers at the median then this would be perfect. $\endgroup$ – Derek 朕會功夫 Oct 1 '15 at 6:19
  • $\begingroup$ Not really, because in that case Hoare's algorithm is $O( N \log N)$, better than quicksort only by a constant factor. $\endgroup$ – Mark Dominus Oct 1 '15 at 11:42
-2
$\begingroup$

Sorting would consume extra time if it was an array with small size.! It would be better if you would just traverse through the array once and keep track of the first smallest and use the first smallest for comparison so that you get 2nd largest. But for an array of large size.. It would be better to sort using some algorithms like heap sort, merge sort or heap sort.. Because, if the smallest element in the array would be at the end of the array, it will take you O(n) time.

$\endgroup$
  • 1
    $\begingroup$ Can you offer any evidence for your approach being actually faster? Aren't you focusing on the best case (for your algorithm) a bit too much? $\endgroup$ – Raphael Apr 12 '16 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.