find the largest ten numbers in an array in C

Question

I have an array of int (the length of the array can go from 11 to 500) and i need to extract, in another array, the largest ten numbers.

So, my starting code could be this:

arrayNumbers[n]; //array in input with numbers, 11<n<500

int arrayMax[10];

for (int i=0; i<n; i++){

    if(arrayNumbers[i] ....

    //here, i need the code to save current int in arrayMax correctly
}

//at the end of cycle, i want to have in arrayMax, the ten largest numbers (they haven't to be ordered)

What's the best efficient way to do this in C?

Answer 1

Study maxheap. Maintain a heap of size 10 and ignore all spilling elements. If you face a difficulty please ask.

EDIT: If number of elements are less than 20, find n-10 smallest elements and rest if the numbers are top 10 numbers.

Visualize a heap here

EDIT2: Based on comment from Sleepy head, I searched and found this (I have not tested). You can find kth largest element (10 in this case) in )(n) time. Now in O(n) time, you can find first 10 elements which are greater than or equal to this kth largest number. Final complexity is linear.

Answer 2

Here is a algo which solves in linear time:

1. Use the selection algorithm, which effectively find the k-th element in a un-sorted array in linear time. You can either use a variant of quick sort or more robust algorithms.

2. Get the top k using the pivot got in step 1.

Answer 3

This is my idea:

1. insert first 10 elements of your arrayNum into arrMax.
2. Sort those 10 elements arrMax[0] = min , arrMax[9] = max.
3. then check the remaining elements one by one and insert every possible candidate into it's right position as follow (draft):

int k, r, p;

    for (int k = 10; k < n; k++)
   {
    r = 0;
    while(1)
    {
    if (arrMax[r] > arrNum[k]) break; // position to insert new comer
    else if (r == 10) break;  // don't exceed length of arrMax
    else r++;                 // iteration
    }

    if (r != 0)  // no need to insert number smaller than all members
    {
     for (p=0; p<r-1; p++) arrMax[p]=arrMax[p+1]; // shift arrMax to make space for new comer
     arrMax[r-1] = arrNum[k]; // insert new comer at it's position
    }
   } // done!

Answer 4

Sort the array and insert Max 10 elements in another array

Answer 5

you can use the "select" algorithm which finds you the i-th largest number (you can put any number you like instead of i) and then iterate over the array and find the numbers that are bigger than i. in your case i=10 of course..

Answer 6

The following example can help you. it arranges the biggest 10 elements of the original array into arrMax assuming you have all positive numbers in the original array arrNum. Based on this you can work for negative numbers also by initializing all elements of the arrMax with possible smallest number.

Anyway, using a heap of 10 elements is a better solution rather than this one.

void main()
{
int arrNum[500]={1,2,3,21,34,4,5,6,7,87,8,9,10,11,12,13,14,15,16,17,18,19,20};
int arrMax[10]={0};

int i,cur,j,nn=23,pos;
clrscr();

for(cur=0;cur<nn;cur++)
{
    for(pos=9;pos>=0;pos--)
       if(arrMax[pos]<arrNum[cur])
         break;
    for(j=1;j<=pos;j++)
       arrMax[j-1]=arrMax[j];
    if(pos>=0)
       arrMax[pos]=arrNum[cur];
}

for(i=0;i<10;i++)
   printf("%d ",arrMax[i]);

getch();
}

Answer 7

When improving efficiency of an algorithm, it is often best (and instructive) to start with a naive implementation and improve it. Since in your question you obviously don't even have that, efficiency is perhaps a moot point.

If you start with the simpler question of how to find the largest integer:

1. Initialise largest_found to INT_MIN

2. Iterate the array with :

   IF value > largest_found THEN largest_found = value

To get the 10 largest, you perform the same algorithm 10 times, but retaining the last_largest and its index from the previous iteration, modify the largest_found test thus:

IF value > largest_found && 
   value <= last_largest_found &&
   index != last_largest_index 
THEN
   largest_found = last_largest_found = value
   last_largest_index = index

Start with that, then ask yourself (or here) about efficiency.