if in an unsorted array we have 1000 distinct elements then what are the minimum number of comparisons needed to get second smallest elements in the array(worst case)..can any one give algorithm used here???
what will be the number of comparisons for largest will it be n-1 or some thing else
we can further do it in n-1 by maintaining an array for the elements which we swap whenever we find a smallest element. n-1 comparisons are required for such an array and in that array the element in last but 1 position is the second smallest. cant we do it this way when space is not of concern??? pls correct me
Start with comparing elements of the array in odd and even positions and determining largest element of each pair. Now you’ve got only n/2 elements. Continue pairwise comparisons to get n/4, n/8, … elements. Stop when the largest element is found. This step requires n-1 comparisons.
During previous step, the largest element was immediately compared with log(n) other elements. You can determine the largest of these elements in log(n)-1 comparisons. That would be the second-largest number in the array.