🚀 go-pugleaf

Well, it seems to me as if this algo just doesn't do the job... The problem
is that in your example the 2 biggest values are in the upper half of your
list of numbers... So, when you divide the list in 2, it will return the
biggest numbers of each of the halves... and not the biggest numbers of the
entire list...

If you definitly wanted to work recursively... Try the same algo, but return
only the biggest value and then reapply the algo to the same list, but with
the biggest value removed... Otherwise, just plainly run through the entire
list and keep the 2 biggest values in 2 variables...

Andy


"Bart Vandewoestyne" <Bart.Vandewoestyne@skynet.be> wrote in message
news:3A11B99A.2BB2E1E7@skynet.be...
> I am trying to write a program that implements an algorithm to find the
two
> largest integers out of a row of numbers.
> My algorithm should work this way:
>
> The number of elements in the row is a power of 2.
>
> I separate the row in two halves, and then i apply the same algorithm
recursivly
> to the two new rows.  If I have the two biggest numbers of these new rows,
then
> i can find the two biggest of the total with maximum 2 comparisons.
>
> The alorithm I implemented so far is located at:
>
> http://users.skynet.be/vandewoestyne/downloads/Searcher.java
>
> and
>
> http://users.skynet.be/vandewoestyne/downloads/BigThings.java
>
> But it seems to have a mistake in it, because this was an example of an
> incorrect output I got ('links' = left, 'rechts' = right, 'Grootste waarde
=
> Biggest value', 'Tweede grootste waarde='second largest value'):
>
> Heaven:~/projecten/ontwerpen02$ java Searcher
> 78 67 51 15 34 28 31 53 35 50 68 1 33 92 95 13
>
> links : 78 67 51 15 34 28 31 53
> rechts: 35 50 68 1 33 92 95 13
> links : 78 67 51 15
> rechts: 34 28 31 53
> links : 78 67
> rechts: 51 15
> links : 34 28
> rechts: 31 53
> links : 35 50 68 1
> rechts: 33 92 95 13
> links : 35 50
> rechts: 68 1
> links : 33 92
> rechts: 95 13
> Grootste waarde:        95
>
> Tweede grootste waarde: 78
>
> --
> Ing. Bart Vandewoestyne   Bart.Vandewoestyne@skynet.be
> Hugo Verrieststraat 48        GSM: +32 (0)478 397 697
> B-8550 Zwevegem http://hello.to/MC303
> ----------------------------------------------------------------------
> "Any fool can know, the point is to understand." - Albert Einstein

Andy Zaidman wrote:
>
> If you definitly wanted to work recursively...

Yes, I do.

> Try the same algo, but return
> only the biggest value and then reapply the algo to the same list, but with
> the biggest value removed...

Hmm... that is not exactly what I want to do...
The point in my algo is that if I have 4 values, say p1>p2 (found from left
side) and q1>q2 (found from right side), then i can find the two biggest numbers
from (left+right) side by:

if (p1>q1) then {
	p1 is biggest in (left+right);
	if (p2>q1) then p2 is second_biggest else q1 is second_biggest
}
else {
	q1 is biggest;
	if (q2>p1) then q2 is second_biggest else p1 is second_biggest
}

This will always result in a maximum of 2 comparisons.

> Otherwise, just plainly run through the entire
> list and keep the 2 biggest values in 2 variables...

That is not what I want to do.  I want to implement the recursive algorithm.

I will try to check my program and correct it, but in the meanwhile, I
appriciate some more feedback on what exactly I should change...

Thanx,
mc303

-- 
Ing. Bart Vandewoestyne			  Bart.Vandewoestyne@skynet.be
Hugo Verrieststraat 48			       GSM: +32 (0)478 397 697
B-8550 Zwevegem					 http://hello.to/MC303
----------------------------------------------------------------------
"Any fool can know, the point is to understand." - Albert Einstein

Bart Vandewoestyne a �crit :
> 
> Andy Zaidman wrote:
> >
> > If you definitly wanted to work recursively...
> 
> Yes, I do.
> 
> > Try the same algo, but return
> > only the biggest value and then reapply the algo to the same list, but with
> > the biggest value removed...
> 
> Hmm... that is not exactly what I want to do...
> The point in my algo is that if I have 4 values, say p1>p2 (found from left
> side) and q1>q2 (found from right side), then i can find the two biggest numbers
> from (left+right) side by:
> 
> if (p1>q1) then {
>         p1 is biggest in (left+right);
>         if (p2>q1) then p2 is second_biggest else q1 is second_biggest
> }
> else {
>         q1 is biggest;
>         if (q2>p1) then q2 is second_biggest else p1 is second_biggest
> }
> 
> This will always result in a maximum of 2 comparisons.
> 
> > Otherwise, just plainly run through the entire
> > list and keep the 2 biggest values in 2 variables...
> 

Hi,

> That is not what I want to do.  I want to implement the recursive algorithm.

Ok, look at a linear algorithm, and if realy you still want to implement a
recursive one, you can still use this example and call it with variable 
search limits.

    final static int MIN = -9999999;

    public static void main(String[] args) 
    {
      int first = MIN;
      int second = MIN;
      int[] list = {78, 67, 51, 15, 34, 28, 31, 53, 35, 50, 68, 1, 33, 92, 95, 13};

      int size = list.length;
      for(int i=0;i<size;i++)
      {
        final int n = list[i];
        if(n>first) {
            second = first;
            first = n;
        }
        else if(n>second)
        {
            second = n;
        }
      }

      System.out.println(first);
      System.out.println(second);
    }

regards,

Marc

_____________________________________________________________________

  L  U  D  O  M  E  D  I  A                   http://www.ludomedia.ch
  -------------------------                 Phone: ++ 41 21 634.80.88
  W E B - S O L U T I O N S                mailto:marnic@ludomedia.ch
_____________________________________________________________________

Andy Georges heeft gelijk, zoeken in een niet-gesorteerde rij is altijd
O(n)... Waarom wil je per se recursief werken?

Andy

>
> Hi,
>
> > That is not what I want to do.  I want to implement the recursive
algorithm.
Why? this can often lead to ugly StackOverflow exceptions..

Why easy if you can do it the hard way?

I should create a database with a table (CREATE TABLE...), and put al the
numbers into it by running through the elements and inserting them into a
table (INSERT INTO table (number) VALUE ..).  On the insert I should write a
trigger to check if the number exists allready in the database.  If so, I do
not execute the insert.
Then I should write an SQL-statement to get the biggest number (SELECT
MAX(number)..).  Second I should write a select to get the second number
(SELECT MAX(number) FROM table WHERE number < biggestnumber).
When I got all this, I should go through the table (SELECT * FROM TABLE
ORDER BY number) and delete each element (DELETE FROM TABLE WHERE number =
..).
At the end I should drop the index (DROP INDEX...) and the table (DROP
TABLE..).

Then I should write a program to do it the easy way, just run through the
array.


Bart Vandewoestyne wrote in message <3A11B99A.2BB2E1E7@skynet.be>...
>I am trying to write a program that implements an algorithm to find the two
>largest integers out of a row of numbers.
>My algorithm should work this way:
>
>The number of elements in the row is a power of 2.
>
>I separate the row in two halves, and then i apply the same algorithm
recursivly
>to the two new rows.  If I have the two biggest numbers of these new rows,
then
>i can find the two biggest of the total with maximum 2 comparisons.
>
>The alorithm I implemented so far is located at:
>
>http://users.skynet.be/vandewoestyne/downloads/Searcher.java
>
>and
>
>http://users.skynet.be/vandewoestyne/downloads/BigThings.java
>
>But it seems to have a mistake in it, because this was an example of an
>incorrect output I got ('links' = left, 'rechts' = right, 'Grootste waarde
=
>Biggest value', 'Tweede grootste waarde='second largest value'):
>
>Heaven:~/projecten/ontwerpen02$ java Searcher
>78 67 51 15 34 28 31 53 35 50 68 1 33 92 95 13
>
>links : 78 67 51 15 34 28 31 53
>rechts: 35 50 68 1 33 92 95 13
>links : 78 67 51 15
>rechts: 34 28 31 53
>links : 78 67
>rechts: 51 15
>links : 34 28
>rechts: 31 53
>links : 35 50 68 1
>rechts: 33 92 95 13
>links : 35 50
>rechts: 68 1
>links : 33 92
>rechts: 95 13
>Grootste waarde:        95
>
>Tweede grootste waarde: 78
>
>--
>Ing. Bart Vandewoestyne   Bart.Vandewoestyne@skynet.be
>Hugo Verrieststraat 48        GSM: +32 (0)478 397 697
>B-8550 Zwevegem http://hello.to/MC303
>----------------------------------------------------------------------
>"Any fool can know, the point is to understand." - Albert Einstein

>     final static int MIN = -9999999;
>
>     public static void main(String[] args)
>     {
>       int first = MIN;
>       int second = MIN;
>       int[] list = {78, 67, 51, 15, 34, 28, 31, 53, 35, 50, 68, 1, 33, 92,
95, 13};
<snip>

I'd use int first = Integer.MIN_INFINITY;

Omdat dat moet van de docent? ;-)

"Andy Zaidman" <Andy.Zaidman@(nospam)Bigfoot.com> wrote in message
news:8utlpa$3r5$1@news0.skynet.be...
> Andy Georges heeft gelijk, zoeken in een niet-gesorteerde rij is altijd
> O(n)... Waarom wil je per se recursief werken?
>
> Andy
>
>

Andy Zaidman wrote:
> 
> Andy Georges heeft gelijk, zoeken in een niet-gesorteerde rij is altijd
> O(n)... Waarom wil je per se recursief werken?

Because my algorithm would require less comparisons...

Greetzzz,
mc303

-- 
Ing. Bart Vandewoestyne			  Bart.Vandewoestyne@skynet.be
Hugo Verrieststraat 48			       GSM: +32 (0)478 397 697
B-8550 Zwevegem					 http://hello.to/MC303
----------------------------------------------------------------------
"Any fool can know, the point is to understand." - Albert Einstein

Yvo Volders wrote:
> 
> Why easy if you can do it the hard way?

Because it is an educational example ;-)

<SNIP HARD WAY>
>
> Then I should write a program to do it the easy way, just run through the
> array.

LOL
Tnx for the hint, but I think I will continue using _my_ 'hard way' ;-)

Greetzzz,
mc303

-- 
Ing. Bart Vandewoestyne			  Bart.Vandewoestyne@skynet.be
Hugo Verrieststraat 48			       GSM: +32 (0)478 397 697
B-8550 Zwevegem					 http://hello.to/MC303
----------------------------------------------------------------------
"Any fool can know, the point is to understand." - Albert Einstein

Bart Vandewoestyne <

> > Andy Georges heeft gelijk, zoeken in een niet-gesorteerde rij is altijd
> > O(n)... Waarom wil je per se recursief werken?
>
> Because my algorithm would require less comparisons...

got any proof of that?

Andy Zaidman wrote:
> 
> Well, it seems to me as if this algo just doesn't do the job... The problem
> is that in your example the 2 biggest values are in the upper half of your
> list of numbers... So, when you divide the list in 2, it will return the
> biggest numbers of each of the halves... and not the biggest numbers of the
> entire list...

OK, I think I have found my problem:

I should replace this...
	
<BEGIN OLD CODE>
	
	    /* 
	     * Recursive function call on left and right side
	     */
	    BigThings leftBigThings = left.searchTwoBiggest();
	    BigThings rightBigThings = right.searchTwoBiggest();
	    
	    if (leftBigThings.getBiggest()>rightBigThings.getBiggest()) {
		$values.setBiggest(leftBigThings.getBiggest());
		if (leftBigThings.getSecondBiggest()>rightBigThings.getBiggest())
		    $values.setSecondBiggest(leftBigThings.getSecondBiggest());
	    }
	    else {
		$values.setBiggest(rightBigThings.getBiggest());
		if (rightBigThings.getSecondBiggest()>leftBigThings.getBiggest())
		    $values.setSecondBiggest(rightBigThings.getSecondBiggest());
	    }
	}

<END OLD CODE>

With this...

<BEGIN NEW CODE>
	
	    /* 
	     * Recursive function call on left and right side
	     */
	    BigThings leftBigThings = left.searchTwoBiggest();
	    BigThings rightBigThings = right.searchTwoBiggest();
	    
	    if (leftBigThings.getBiggest()>rightBigThings.getBiggest()) {
		$values.setBiggest(leftBigThings.getBiggest());
		if (leftBigThings.getSecondBiggest()>rightBigThings.getBiggest())
		    $values.setSecondBiggest(leftBigThings.getSecondBiggest());
		else
		    $values.setSecondBiggest(rightBigThings.getBiggest());
	    }
	    else {
		$values.setBiggest(rightBigThings.getBiggest());
		if (rightBigThings.getSecondBiggest()>leftBigThings.getBiggest())
		    $values.setSecondBiggest(rightBigThings.getSecondBiggest());
		else 
		    $values.setSecondBiggest(leftBigThings.getBiggest());
	    } 

<END NEW CODE>

I think adding these two 'else' clauses at the end of both cases solves my
problem because this way the second biggest value is always set.
Could somebody verify this?

Greetzzz,
mc303

--
Ing. Bart Vandewoestyne			  Bart.Vandewoestyne@skynet.be
Hugo Verrieststraat 48			       GSM: +32 (0)478 397 697
B-8550 Zwevegem					 http://hello.to/MC303
----------------------------------------------------------------------
"Any fool can know, the point is to understand." - Albert Einstein

>> Andy Georges heeft gelijk, zoeken in een niet-gesorteerde rij is altijd
>> O(n)... Waarom wil je per se recursief werken?

>Because my algorithm would require less comparisons...

Is dat zo? En zelf als ... het blijven branches, en bij een loop-if-branch
heb je nog kans dat de zaak binnen een cacheline blijft.

Armin
--
Philips Semiconductors B.V.
Systems Laboratory Eindhoven (PS-SLE)

Backup not found: (A)bort (R)etry (P)anic

Tools:
http://www.phys.uu.nl/~gerritsn/download.html