How to Design an Algorithm?

[One Pea]

This may be a very open ended question, but I am learning algorithms for the first time. I have been given the problem "Find two largest elements in an array with n elements in 1.5n comparisons". I have to start by designing an algorithm, but I am not sure where or how to begin?

[keskiverto]

How would you find the largest element from the array?
How many comparisons does that require?

[One Pea]

n-1 comparisons?

[John87Connor]

X = Y = array[0]

for each value in array ...
if value > Y ... then X = Y, Y = value

needs only n comparisons
the previously highest value will be stored in X (shifted from Y), and Y will be the highest number ... or is that wrong?

[tpb]

John87Connor wrote:

or is that wrong

If a value is greater than the second greatest but not the first greatest then your algorithm won't set the second greatest to it since you only test if it's greater than the first greatest.

And I don't think initializing them both to a[0] is correct, either. It's probably best to initialize them to INT_MIN.

[keskiverto]

It's probably best to initialize them to INT_MIN.

Consider

maxtwo( const Foo* array, size_t size ) {
  Foo X = INT_MIN; // Is this best, or even legal?
  Foo X = std::numeric_limits<Foo>::min(); // Any better? 

The logic of algorithm should not depend on the type of the elements. (Obviously, one can have no such algorithm for non-comparable types.)


There can be special cases and decisions:
* What if array has less than 2 elements?
* What is the correct output for { 2, 1, 2 }?

[jonnin]

n elements in 1.5n comparisons
^^
Should be able to do it in N (-1 whatever) which you already knew when asked directly. the question is flawed.

the code snips are nice but not tied to an algorithm. An algorithm does not care about code, language, data types, etc... its just the steps you will take.

[keskiverto]

Should be able to do it in N

The "two largest" with N comparisons?

The largest you can get with N (or N-1) comparisons, but does that alone solve the second largest for you?

[jonnin]

yes.

when you find one bigger than largest, move (old) largest to next largest first, then replace largest. no comparison required to do that.

[lastchance]

What is the significance of the 1.5?

If N >= 2 then you will require somewhere between N-1 and 2N-3 comparisons (I think), but it depends on the array.

Are you hoping for 1.5N on average?

Also, are you after the two largest VALUES (which isn't ambiguous) or the positions of the two largest values (which is)?

First step of algorithm: clarify the problem!

[tpb]

jonnin wrote:

when you find one bigger than largest, move (old) largest to next largest first, then replace largest. no comparison required to do that.

I already explained why that is wrong. You can't just compare to the largest. What if a value is larger than the second largest but not larger than the first largest? That's why it takes more than n, although it usually takes closer to 1.1n than 1.5n. But as lastchance said it's basically between n and 2n, so apparently 1.5n is some kind of average.

The algorithm compares the current value to the second largest and if it's larger than that then compares it to the first largest.

if val > next_largest:
    if val > largest:
        next_largest = largest
        largest = val
    else
        next_largest = val

[jonnin]

That is correct, I was wrong.

I believe a simple
1 2 3 4 5 6

is the worst case, requries ~2n with the above logic (2n -1 or whatever for the freebies).