# Software Programming

Kunuk Nykjaer

## Interview-question: Find two largest elements in array of size n – C# example

with one comment

Design an algorithm to find the two largest elements in a sequence of n numbers.
Number of comparisons need to be O(n) + O(log n)

You use a tournament sort.
Here’s an example in C#

Program.cs

```using System;
using System.Collections.Generic;
using System.Linq;

/// <summary>
/// Author: Kunuk Nykjaer
/// Tournament Sort example
/// http://en.wikipedia.org/wiki/Tournament_sort
/// </summary>
class Program
{
class P
{
public int Strength { get; set; }
public List<int> Opponents { get; private set; }
public P()
{
Opponents = new List<int>();
}
}

// Return winner of the match and remember opponent
// O(1)
static P Play(P p1, P p2)
{
if (p1.Strength > p2.Strength)
{
return p1;
}
return p2;
}

// Runtime O(n) + O(logn)
static void Main(string[] args)
{
// Test data setup, even number list
var playerStrengths = new[] { 1, 2, 5, 4, 9, 7, 8, 7, 5, 4, 1, 0, 1, 4, 2, 3 };
var players = playerStrengths.Select(i => new P { Strength = i }).ToList();

// O(n)
while (players.Count > 1)
{
var nextRound = new List<P>();
for (int i = 0; i < players.Count - 1; i += 2)
{
P winner = Play(players[i], players[i + 1]);
}
players = nextRound;
}

// O(1)
var tournamentWinner = players.First();
int first = tournamentWinner.Strength;
int second = -1;

// O(logn)
foreach (int i in tournamentWinner.Opponents)
if (i > second)// update
second = i;

Console.WriteLine("First: {0}, Second: {1}", first, second);
}
}
```

Output is:
First: 9, Second: 8

http://en.wikipedia.org/wiki/Tournament_sort

http://stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-of-comparisom

Written by kunuk Nykjaer

May 25, 2012 at 3:42 pm

Posted in Algorithm, Csharp

Tagged with