Getting an array of max values

[programmer212]

So I have an array of integers. I want to take the biggest integers from that array and put it into a smaller array that just has the biggest integers in it. This is what I have so far.

int array1[20];
int array2[5];

for(int i = 0; i < 20; i++)
{
cin >> array1[i];
}

int max1 = array1[1];

for(int i = 0; i < 5; i++)
{
if( array1[i] > array1[1])
{
array2[i] = array1[i];
}
}

I know this only gives me the max value but I can't wrap my head around getting the biggest values from array1 to array2.

[tpb]

You can do it with the basic idea that you have but you need an outer loop to loop 5 times, first getting the overall max, then the max from the remaining numbers, etc..

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    const int INPUT_SIZE = 20, HIGH_SIZE = 5;
    int a[INPUT_SIZE], b[HIGH_SIZE];

    for (int i = 0; i < INPUT_SIZE; i++) cin >> a[i];

    for (int i = 0; i < HIGH_SIZE; i++) {
        int m = i;
        for (int j = i + 1; j < INPUT_SIZE; j++)
            if (a[j] > a[m])
                m = j;
        int t = a[m]; a[m] = a[i]; a[i] = t;
    }
    copy_n(&a[0], HIGH_SIZE, &b[0]);

    for (int i = 0; i < HIGH_SIZE; i++) cout << b[i] << ' ';
    cout << '\n';
}

Or you could sort the array into non-ascending order and pluck off the first five elements:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    const int INPUT_SIZE = 20, HIGH_SIZE = 5;
    int a[INPUT_SIZE], b[HIGH_SIZE];

    for (int i = 0; i < INPUT_SIZE; i++) cin >> a[i];

    sort(&a[0], &a[INPUT_SIZE], [](int x,int y){return x >= y;});
    copy_n(&a[0], HIGH_SIZE, &b[0]);

    for (auto n: b) cout << n << ' '; cout << '\n';
}

[icy1]

Yep, sorting first comes to mind. If you don't want to modify input array, first copy it over, preferably to a vector. With a vector you can sort descending and then simply call resize(5), and you're done.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Returns biggest n integers of an array as a vector
vector<int> Biggest(int* arr, int arr_size, int n)
{
    vector<int> v(arr, arr+arr_size);
    sort(v.begin(), v.end(), greater<int>());
    v.resize(n);
    return v;
}

int main()
{
    int arr[] = { 69, 17, 2, 23, 73, 61, 52, 98, 30, 92, 
                24, 77, 62, 73, 18, 61, 22, 27, 41, 49 };
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    
    cout << "Initial array:" << endl;
    for (auto& x : arr )
        cout << x << " ";
    cout << endl << endl;
    
    int n = 5;
    cout << "Biggest " << n << " integers:" << endl;
    auto v = Biggest(arr, arr_size, n);
    for (auto& x : v)
        cout << x << " ";
    cout << endl;
    
    return 0;
}

Initial array:
69 17 2 23 73 61 52 98 30 92 24 77 62 73 18 61 22 27 41 49 

Biggest 5 integers:
98 92 77 73 73 

[jonnin]

you can do a 'broken' sort for this.
that is, you can rig some of the sorting algorithms to partially sort so they will correctly cluster values in the general region where they belong, but fall short of actually getting them in 100% numerical order.
so here, you could run 1 pass of quicksort and if I remember it right you would get the highest 50% in the bottom and the lowest 50% in the top.
then you can take ONLY the bottom, and sort that again, and the same is true, the top 50% can be discarded. now you have done 2 iterations and have cut the list from 20 to 10 to 5, and you have your answer, and can skip the final 2 or 3 or whatever it is iterations of the sorting...!!

the difference in performance for only 20 to 5 is insignificant and not worth the trouble, but if you had 20 billion and needed the top 5 billion, the performance increase would be notable.

Just a thought :)

[lastchance]

Maybe you could try std::partial_sort()
http://www.cplusplus.com/reference/algorithm/partial_sort/

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
   const int LONG = 20, SHORT = 5;
   int array1[LONG] = { 1, 7, 23, 22, 0, 6, 4, 33, 99, 56, 32, 12, 6, 11, 19, 88, 77, 3, 18, 45 };
   int array2[SHORT];

   partial_sort( array1, array1 + SHORT, array1 + LONG, []( int a, int b ){ return a > b;} );
   copy( array1, array1 + SHORT, array2 );

   cout << "Top " << SHORT << " elements are ";
   for ( int i : array2 ) cout << i << " ";
}

Top 5 elements are 99 88 77 56 45 

[jonnin]

... this is something I would not have even looked for or expected to exist. But yea, what Lastchance said is where I was going.