Finding largest elements in array efficiently

Question

I have a program that finds the two largest elements of an Array. I have to look at the number of comparisons between elements of the Array to determine efficiency (not big-O) I have determined the worst-case is 2n-3 comparisons (assuming the first two elements are the largest) Here is the function.

Integer[] A = {11,22,8,7,5,6,7,8,1,9};
    int largest = 0;
    int secondLargest = 0;
    int count = 1;
    if (A[0] < A[1]){
        largest = A[1];
        secondLargest = A[0];
    } else {
        largest = A[0];
        secondLargest = A[1];
    }
    for (int i = 2; i < A.length; i++){
        count++;
        if (A[i] > largest) {

            secondLargest = largest;
            largest = A[i];
        } else {
            count++;
            if (A[i] > secondLargest) { 
                secondLargest = A[i];
            }
        }
    }
System.out.println("Largest:" + largest + " Second:" + secondLargest + " count:" + count);

I use count to determine the number of comparisons. Is there any way to reduce the number of worst case comparisons within this function? I can't figure out how to make this function better.

Just pre-sort the array and, technically, you will know its to biggest elements in a constant time! — madhead
– madhead, Commented Oct 26, 2017 at 23:05
Your algorithm appears optimal for the worst case number of operations. — castletheperson
– castletheperson, Commented Oct 26, 2017 at 23:27
By the way, algorithms which find the smallest (or largest) n elements in an array are called partial sorting algorithms. — castletheperson
– castletheperson, Commented Oct 26, 2017 at 23:28

Kenney · Accepted Answer · 2017-10-26 23:21:33Z

2

2n - 3 (via 1 + 2(n-2)) as a worst case is about as good as you can get: you have to look at all n values, and for each of those you have to check against the 2 largest values in the worst case scenario.

You can gain some efficiency if you swap the checks:

if ( A[i] > secondLargest )
{
   if ( A[i] > largest )
     secondLargest = largest,
     largest = A[i];
   else
     secondLargest = A[i];
}

because if a value is not higher than secondLargest, it won't be larger than the largest. In a best case scenario (descending sorted list), this increases the efficiency to n - 3, whereas your algorithm also has 2n - 3 here.

However, the worst case scenario (an ascending sorted list) will still be the same.

answered Oct 26, 2017 at 23:21

Kenney

9,11317 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

sprinter · Accepted Answer · 2017-10-26 23:30:58Z

No matter what algorithm you pick you will be able to come up with scenario where each element has to be compared to the largest and second largest.

However in the more common randomly distributed case you could avoid a lot of comparisons by comparing to the second largest value first. Most elements will be less than the second largest value and will avoid the second comparison.

if (value > secondLargest) {
    secondLargest = value;
    if (secondLargest > largest) {
        int temp = largest;
        largest = secondLargest;
        secondLargest = temp;
    }
}

Or better (IMO):

int[] largest = new int[2];
for (int value: A) {
    if (value > largest[1]) {
        largest[1] = value;
        Arrays.sort(largest); 
    }
}

Note that for small arrays Arrays.sort just does a simple compare and swap.

Collectives™ on Stack Overflow

Finding largest elements in array efficiently

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related