Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
can anybody tell why this code is not giving correct output for finding
second smallest using tournament method?
my approach is same as @Don approach
On Wed, Sep 5, 2012 at 12:16 PM, shashi kant shashiski...@gmail.com wrote:
Heap's good but the i think problem clearly mentions Tournament sort
use this
https://blogs.oracle.com/malkit/entry/finding_kth_minimum_partial_ordering
although you can do a Inplace tournament sort ...swapping the
corresponding elements
level 1. adjacent pairs
level 2: between pairs apart by 1 place n so on (2,4,8..)
until there is only one element left in there without a pair.this
gives u least element
Now instead of using a Multimap , use a simple array with size equal to
original array and store the element that defeated each corresponding
element.
Get all those elements defeated by the least element ... that number
should be of order O(n)
get the second least element out of it in O(n) time.
*Shashi Kant *
*Think positive and find fuel in failure*
http://thinkndoawesome.blogspot.com/
*System/Software Engineer*
*Hewlett-Packard India Software Operations.
*
On Wed, Sep 5, 2012 at 4:11 AM, Dave dave_and_da...@juno.com wrote:
@Don: Nope. Constructing a heap can be done in O(n). See, e.g.,
http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node9.html
.
Dave
On Tuesday, September 4, 2012 10:24:25 AM UTC-5, Don wrote:
Constructing a max-heap is O(n*log n)
However, the problem asked for a solution using tournament method.
If you ignore that requirement, an O(n) solution is trivial, and
doesn't require the additional storage of a heap:
int first = max(A[0], A[1]);
int second = min(A[0], A[1]);
for(i = 2; i N; ++i)
{
if (A[i] = first)
{
second = first;
first = A[i];
}
else if (A[i] second)
second = A[i];
}
// First and second now contain 1st and 2nd largest values in A
Don
On Sep 3, 5:04 am, bharat b bagana.bharatku...@gmail.com wrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/bKzs-wHLSoIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
//To implement tournament code...
#includeiostream.h
#includemath.h
#define size 10
class node
{
public:
char c;
int freq;
int beaten;
node *left,*right;
node *parent;
node(char c1=0,int freq1=0,node *l=0,node *r=0)
{
c=c1;
freq=freq1;
left=l;
right=r;
beaten=freq1;
}
};
class array
{
public:
node *root;
array()
{
root=0;
}
int size1;
int heapsize;
int length;
node *b[size];
node *a[size];
void insert();
void buildheap();
void minheapify(int i);
node* extractmin();
void heapinsert(node *p);
void tour();
void display();
void display1(node *);
void decrease(int i);
void traverse()
{
traverse(root);
}
void traverse(node*);
void minimum();
int left(i)
{
return 2*i;
}
int right(i)
{
return 2*i+1;
}
};
//Min heap
void array::buildheap()
{
heapsize=length;
for(int i=(floor(length/2));i=1;i--)
{
minheapify(i);
}
}
void array::minheapify(int i)
{
int l,r,smallest;
node *temp;
l=left(i);
r=right(i);
if(l=heapsize a[l]-freq a[i]-freq)
{
smallest=l;
}
else
{
smallest=i;
}
if(r=heapsize a[r]-freq a[smallest]-freq)
{
smallest=r;
}
if(smallest!=i)
{
temp=a[i];
a[i]=a[smallest];
a[smallest]=temp;
minheapify(smallest);
}
}
void array::heapinsert(node* k)
{
heapsize=heapsize+1;
a[heapsize]=k;
decrease(heapsize);
}
void array::minimum()
{
couta[1];
}
node* array::extractmin()
{
node* min;
if(heapsize1)
return 0;
min=a[1];
a[1]=a[heapsize];
heapsize=heapsize-1;
minheapify(1);
return min;
}
void array::decrease(int i)
{
node* temp;
while(i1
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
Heap's good but the i think problem clearly mentions Tournament sort
use this
https://blogs.oracle.com/malkit/entry/finding_kth_minimum_partial_ordering
although you can do a Inplace tournament sort ...swapping the corresponding
elements
level 1. adjacent pairs
level 2: between pairs apart by 1 place n so on (2,4,8..)
until there is only one element left in there without a pair.this
gives u least element
Now instead of using a Multimap , use a simple array with size equal to
original array and store the element that defeated each corresponding
element.
Get all those elements defeated by the least element ... that number should
be of order O(n)
get the second least element out of it in O(n) time.
*Shashi Kant *
*Think positive and find fuel in failure*
http://thinkndoawesome.blogspot.com/
*System/Software Engineer*
*Hewlett-Packard India Software Operations.
*
On Wed, Sep 5, 2012 at 4:11 AM, Dave dave_and_da...@juno.com wrote:
@Don: Nope. Constructing a heap can be done in O(n). See, e.g.,
http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node9.html
.
Dave
On Tuesday, September 4, 2012 10:24:25 AM UTC-5, Don wrote:
Constructing a max-heap is O(n*log n)
However, the problem asked for a solution using tournament method.
If you ignore that requirement, an O(n) solution is trivial, and
doesn't require the additional storage of a heap:
int first = max(A[0], A[1]);
int second = min(A[0], A[1]);
for(i = 2; i N; ++i)
{
if (A[i] = first)
{
second = first;
first = A[i];
}
else if (A[i] second)
second = A[i];
}
// First and second now contain 1st and 2nd largest values in A
Don
On Sep 3, 5:04 am, bharat b bagana.bharatku...@gmail.com wrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/bKzs-wHLSoIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@Darpan can you implement it without using the multimap and with the same
(divide and conquar) approach.
On Mon, Sep 3, 2012 at 6:25 PM, Darpan Baweja darpan.bav...@gmail.comwrote:
hope this might helps
code:- http://ideone.com/mtHem
used divide and conquer approach
and stored all the beaten elements in the multimap with key is the element
which has beaten them
with key as winner return maximum element stored in multimap
On Mon, Sep 3, 2012 at 3:31 PM, sangeeta goyal sangeeta15...@gmail.comwrote:
@bharat is it tournament method??
On Mon, Sep 3, 2012 at 2:34 PM, bharat b bagana.bharatku...@gmail.comwrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
On Fri, Aug 31, 2012 at 1:46 AM, Don dondod...@gmail.com wrote:
While the list length is more than one
Take 2 elements from the head
Select the larger of the two
If the smaller is greater than the largest beaten by the larger
Then set the largest beaten by the larger to the value of
the smaller
Add the larger to the tail of the list
When this completes, you'll have one element containing the largest
and second largest values.
typedef struct
{
unsigned int value;
unsigned int largestBeaten;
} element;
unsigned int secondLargest(queueelement elements)
{
while(elements.length() 1)
{
element A = elements.dequeue();
element B = elements.dequeue();
if (A.value B.value) swap(A,B);
if (A.largestBeaten B.value) A.largestBeaten = B.value;
elements.enqueue(A);
}
return queue.head().largestBeaten;
}
On Aug 30, 12:53 pm, sangeeta goyal sangeeta15...@gmail.com wrote:
@Don can you give the algorithm for the same??
how would you implement it??
On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote:
The second largest element is the largest element beaten by the
winner.
So if you implement a tournament in which each element keeps track
of
the largest element it has beaten, you'll get the second largest
naturally.
Don
On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote:
give the algo or program to find second largest element in a list
using
tournament method
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*DARPAN BAWEJA*
*Final year, I.T*
*NIT Allahabad*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
yes could be done by taking struct for each element
struct st{int a; //value of elementint i;
//index of beaten arrayint beaten[90];//contains all beaten
elements beaten by this element }ele[90];
here is the modified code :- http://ideone.com/FqnSq
On Mon, Sep 3, 2012 at 8:10 PM, sangeeta goyal sangeeta15...@gmail.comwrote:
@Darpan can you implement it without using the multimap and with the same
(divide and conquar) approach.
On Mon, Sep 3, 2012 at 6:25 PM, Darpan Baweja darpan.bav...@gmail.comwrote:
hope this might helps
code:- http://ideone.com/mtHem
used divide and conquer approach
and stored all the beaten elements in the multimap with key is the
element which has beaten them
with key as winner return maximum element stored in multimap
On Mon, Sep 3, 2012 at 3:31 PM, sangeeta goyal
sangeeta15...@gmail.comwrote:
@bharat is it tournament method??
On Mon, Sep 3, 2012 at 2:34 PM, bharat b
bagana.bharatku...@gmail.comwrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
On Fri, Aug 31, 2012 at 1:46 AM, Don dondod...@gmail.com wrote:
While the list length is more than one
Take 2 elements from the head
Select the larger of the two
If the smaller is greater than the largest beaten by the larger
Then set the largest beaten by the larger to the value of
the smaller
Add the larger to the tail of the list
When this completes, you'll have one element containing the largest
and second largest values.
typedef struct
{
unsigned int value;
unsigned int largestBeaten;
} element;
unsigned int secondLargest(queueelement elements)
{
while(elements.length() 1)
{
element A = elements.dequeue();
element B = elements.dequeue();
if (A.value B.value) swap(A,B);
if (A.largestBeaten B.value) A.largestBeaten = B.value;
elements.enqueue(A);
}
return queue.head().largestBeaten;
}
On Aug 30, 12:53 pm, sangeeta goyal sangeeta15...@gmail.com wrote:
@Don can you give the algorithm for the same??
how would you implement it??
On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote:
The second largest element is the largest element beaten by the
winner.
So if you implement a tournament in which each element keeps track
of
the largest element it has beaten, you'll get the second largest
naturally.
Don
On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote:
give the algo or program to find second largest element in a
list using
tournament method
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*DARPAN BAWEJA*
*Final year, I.T*
*NIT Allahabad*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*DARPAN BAWEJA*
*Final year, I.T*
*NIT Allahabad*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
[algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
Constructing a max-heap is O(n*log n)
However, the problem asked for a solution using tournament method.
If you ignore that requirement, an O(n) solution is trivial, and
doesn't require the additional storage of a heap:
int first = max(A[0], A[1]);
int second = min(A[0], A[1]);
for(i = 2; i N; ++i)
{
if (A[i] = first)
{
second = first;
first = A[i];
}
else if (A[i] second)
second = A[i];
}
// First and second now contain 1st and 2nd largest values in A
Don
On Sep 3, 5:04 am, bharat b bagana.bharatku...@gmail.com wrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@Don nice solution using max heap.it is very simpler to understand
On Tue, Sep 4, 2012 at 8:54 PM, Don dondod...@gmail.com wrote:
Constructing a max-heap is O(n*log n)
However, the problem asked for a solution using tournament method.
If you ignore that requirement, an O(n) solution is trivial, and
doesn't require the additional storage of a heap:
int first = max(A[0], A[1]);
int second = min(A[0], A[1]);
for(i = 2; i N; ++i)
{
if (A[i] = first)
{
second = first;
first = A[i];
}
else if (A[i] second)
second = A[i];
}
// First and second now contain 1st and 2nd largest values in A
Don
On Sep 3, 5:04 am, bharat b bagana.bharatku...@gmail.com wrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@Don: Nope. Constructing a heap can be done in O(n). See, e.g.,
http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node9.html
.
Dave
On Tuesday, September 4, 2012 10:24:25 AM UTC-5, Don wrote:
Constructing a max-heap is O(n*log n)
However, the problem asked for a solution using tournament method.
If you ignore that requirement, an O(n) solution is trivial, and
doesn't require the additional storage of a heap:
int first = max(A[0], A[1]);
int second = min(A[0], A[1]);
for(i = 2; i N; ++i)
{
if (A[i] = first)
{
second = first;
first = A[i];
}
else if (A[i] second)
second = A[i];
}
// First and second now contain 1st and 2nd largest values in A
Don
On Sep 3, 5:04 am, bharat b bagana.bharatku...@gmail.com wrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/bKzs-wHLSoIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@bharat is it tournament method??
On Mon, Sep 3, 2012 at 2:34 PM, bharat b bagana.bharatku...@gmail.comwrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
On Fri, Aug 31, 2012 at 1:46 AM, Don dondod...@gmail.com wrote:
While the list length is more than one
Take 2 elements from the head
Select the larger of the two
If the smaller is greater than the largest beaten by the larger
Then set the largest beaten by the larger to the value of
the smaller
Add the larger to the tail of the list
When this completes, you'll have one element containing the largest
and second largest values.
typedef struct
{
unsigned int value;
unsigned int largestBeaten;
} element;
unsigned int secondLargest(queueelement elements)
{
while(elements.length() 1)
{
element A = elements.dequeue();
element B = elements.dequeue();
if (A.value B.value) swap(A,B);
if (A.largestBeaten B.value) A.largestBeaten = B.value;
elements.enqueue(A);
}
return queue.head().largestBeaten;
}
On Aug 30, 12:53 pm, sangeeta goyal sangeeta15...@gmail.com wrote:
@Don can you give the algorithm for the same??
how would you implement it??
On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote:
The second largest element is the largest element beaten by the
winner.
So if you implement a tournament in which each element keeps track of
the largest element it has beaten, you'll get the second largest
naturally.
Don
On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote:
give the algo or program to find second largest element in a list
using
tournament method
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
The second largest element is the largest element beaten by the winner. So if you implement a tournament in which each element keeps track of the largest element it has beaten, you'll get the second largest naturally. Don On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote: give the algo or program to find second largest element in a list using tournament method -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@Don can you give the algorithm for the same?? how would you implement it?? On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote: The second largest element is the largest element beaten by the winner. So if you implement a tournament in which each element keeps track of the largest element it has beaten, you'll get the second largest naturally. Don On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote: give the algo or program to find second largest element in a list using tournament method -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@sangeeta: n-1 comparison required to choose winner. By tournament approach winner has played match with logn team and winner must have beaten second largest element. So among logn number we can select maximum in logn - 1 comparison. So total comparison required is: n + logn -2 On Thu, Aug 30, 2012 at 10:23 PM, sangeeta goyal sangeeta15...@gmail.comwrote: @Don can you give the algorithm for the same?? how would you implement it?? On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote: The second largest element is the largest element beaten by the winner. So if you implement a tournament in which each element keeps track of the largest element it has beaten, you'll get the second largest naturally. Don On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote: give the algo or program to find second largest element in a list using tournament method -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
While the list length is more than one
Take 2 elements from the head
Select the larger of the two
If the smaller is greater than the largest beaten by the larger
Then set the largest beaten by the larger to the value of
the smaller
Add the larger to the tail of the list
When this completes, you'll have one element containing the largest
and second largest values.
typedef struct
{
unsigned int value;
unsigned int largestBeaten;
} element;
unsigned int secondLargest(queueelement elements)
{
while(elements.length() 1)
{
element A = elements.dequeue();
element B = elements.dequeue();
if (A.value B.value) swap(A,B);
if (A.largestBeaten B.value) A.largestBeaten = B.value;
elements.enqueue(A);
}
return queue.head().largestBeaten;
}
On Aug 30, 12:53 pm, sangeeta goyal sangeeta15...@gmail.com wrote:
@Don can you give the algorithm for the same??
how would you implement it??
On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote:
The second largest element is the largest element beaten by the
winner.
So if you implement a tournament in which each element keeps track of
the largest element it has beaten, you'll get the second largest
naturally.
Don
On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote:
give the algo or program to find second largest element in a list using
tournament method
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
