Find the second smallest element in an array

Given an array with n numbers, with n - 1 comparisons, we are able to find the smallest number in the array. After we find out the minimum number of the array, we only need n - 2 comparisons to find out the second smallest element in the array. Because there are n - 1 remaining elements.

Can we do better than this?

The answer is YES.

The algorithm works as follows. See the image below.
1) Split the array into groups of two.
2) Get the smaller one out of the two.
3) Keep comparing until we find out the minimum. There are n - 1 comparisons to find out the minimum of the array.
4) Note that the second smallest element is among the elements that were compared with the minimum in the comparison tree. There are lgn elements that are compare with the smallest element. See the double circled elements in the image. Now lgn -1 comparisons are needed to find the smallest value out of the lgn values.



The total comparisons  are n - 1 + lgn - 1 = n + lgn - 2.


Comments

Post a Comment

Popular posts from this blog

Can I name a method with the same name of the class in Java?

Can a class have a method with the same name of the class in Java? The answer is yes. See the example below. Public class MyClass { public MyClass() { } public void MyClass() { System.out.println("I have the same name as the class!"); } } You could definitely name a method with the name of the class. As a rule of thumb, you should not capitalize the first letter of the name of your method, though.
Read more

What is new in Java 8

1.  There are default methods and static methods in interfaces in Java 8. 2. Lamdas   Collections . sort ( list , ( o1 , o2 ) -> o1 . getTime () - o2 . getTime ()); Pre-Java8 Collections . sort ( list , new Comparator < Message >() { @Override public int compare ( Message o1 , Message o2 ) { return o1 . getTime () - o2 . getTime (); } });
Read more

Quicksort Java implementation

import java.util.Arrays; public class QuickSort { int [] data ; public void quicksort( int [] nums) { if (nums == null || nums. length == 0 ) return ; data = nums; sort( 0 , nums. length - 1 ); } private void sort( int left, int right) { if (right <= left) return ; int pivot = partition(left, right); sort(left, pivot - 1 ); sort(pivot + 1 , right); } /** * put all the numbers that are smaller than pivot to the left * **/ int partition( int left, int right) { int pivot = data [right]; int startIndex = left; for ( int i = left; i < right; i++) { //all the nums on the left of startIndex are smaller than pivot //the number at startIndex is >= pivot if ( data [i] < pivot) { swap(startIndex++, i); } } // put the pivot to the right position swap(startIndex, right); r...
Read more