Top 5 values from three given arrays

algorithm, c#, sorting

Solution

An easy way with LINQ:

int[] top5 = array1.Concat(array2).Concat(array3).OrderByDescending(i => i).Take(5).ToArray();

An optimal way:

 List<int> highests = new List<int>(); // Keep the current top 5 sorted
 // Traverse each array. No need to put them together in an int[][]..it's just for simplicity
 foreach (int[] array in new int[][] { array1, array2, array3 }) {
     foreach (int i in array) {
         int index = highests.BinarySearch(i); // where should i be?

         if (highests.Count < 5) { // if not 5 yet, add anyway
             if (index < 0) {
                highests.Insert(~index, i);
             } else { //add (duplicate)
                highests.Insert(index, i);
             }
         }
         else if (index < 0) { // not in top-5 yet, add
             highests.Insert(~index, i);
             highests.RemoveAt(0);
         } else if (index > 0) { // already in top-5, add (duplicate)
             highests.Insert(index, i);
             highests.RemoveAt(0);
         }
     }
 }

Keep a sorted list of the top-5 and traverse each array just once.

You may even check the lowest of the top-5 each time, avoiding the BinarySearch:

 List<int> highests = new List<int>();
 foreach (int[] array in new int[][] { array1, array2, array3 }) {
     foreach (int i in array) {
         int index = highests.BinarySearch(i);
         if (highests.Count < 5) { // if not 5 yet, add anyway
             if (index < 0) {                    
                highests.Insert(~index, i);
             } else { //add (duplicate)
                highests.Insert(index, i);
             }
         } else if (highests.First() < i) { // if larger than lowest top-5                
             if (index < 0) { // not in top-5 yet, add
                highests.Insert(~index, i);
                highests.RemoveAt(0);
             } else { // already in top-5, add (duplicate)
                highests.Insert(index, i);
                highests.RemoveAt(0);
             }
         }
     }
}

Problem

Original source