largest n sorted elements from txt file

[nlstmn]

I am required to write a program which finds the largest n numbers in a txt file and prints these largest n numbers in descending order. program must take n from the user.
f.e.:
3, 2, 1, 0, 4, 5, 12, 54, 12, 3, 654, 11, 46, 7, 3
The output for n = 5 should be: 654 54 46 12 12 11
the important part is that I need to come up with the most efficient solution with respect to time. assume that n < 100.
and i am not allowed to use third party libraries
================================================
MINE SOLUTION:
so I opened the txt file and printed the maximum value to the screen and also calculated the total number in the file.
my idea is to get "n" input from the user(n should be < 100), find n largest elements from the initial array which I created and then copy these elements to second array. then I will use heap sorting for the 2nd array.
but I stucked with the part where i find the n maximum elements and copying it to array. please help,where are my mistakes?

#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

void f();
int num_of_numbers = 0, counter = 0;

int main(){
int num_of_numbers = 0, counter = 0;
int max;
int line;
fstream file;
file.open("fd.txt");

if(file.fail()){
cerr << "Error opening the file" << endl;
exit(1);
}

while(file >> line){
if (line > max) max = line;
counter++;
++num_of_numbers;
}
cout << "The maximum is " << max << endl;
cout << "There is totally " << num_of_numbers << " numbers in the text file" << endl;
cout << "============" << endl;
f();
file.close();
return 0;
}

void f(){
int arr[num_of_numbers];
int* second_arr = new int[100];
int maxi, i;
for(int j = 0; j < arr[num_of_numbers]; num_of_numbers++){
if(i > maxi){
maxi = i;
counter++;
}
for(int p = 0; p < 100; p++){
second_arr[p] = maxi;
}
}
cout << "The allocated maximum is " << max << endl;
}

[gunnerfunner]

Read numbers from file to std::set<int>
Split the std::set<int> into left and right, the latter holding N largest numbers
Print the right set in ascending or descending order

#include <iostream>
#include <fstream>
#include <set>
#include <iterator>

using namespace std;
int main()
{
    ifstream inFile ("C:\\test.txt");
    set<int> numbers;

    if(inFile)
    {
        int a;
        while(inFile >> a)
        {
            numbers.insert(a);
        }
    }

    for(auto& elem : numbers)
    {
        cout << elem <<'\t';
    }
    cout << '\n';

    cout << "Choose N: \n";
    int N;
    cin >> N;

    if(N > numbers.size())
    {
        cout << "Too few numbers \n";
    }
    else
    {
        auto highN = std::next(numbers.begin(), numbers.size() - N );

        set<int> left(numbers.begin(), highN), right(highN, numbers.end());

        for(auto& elem : right)
        {
            cout << elem << '\t';////largest N numbers in ascending order;
        }
        cout << '\n';

        for (set<int>::const_reverse_iterator itr = right.rbegin(); itr != right.rend(); ++itr)
        {
            cout << *itr << '\t'; //largest N numbers in descending order;
        }
    }
}

Sample File
1 2 3 4 5 6 7 8 9 11 12 23 12 98 34
Program Output

1       2       3       4       5       6       7       8       9       11
12      23      34      98
Choose N:
4
12      23      34      98
98      34      23      12
Process returned 0 (0x0)   execution time : 2.110 s
Press any key to continue.

[JLBorges]

> my idea is to get "n" input from the user(n should be < 100), find n largest elements from the initial array
> then copy these elements to second array. then I will use heap sorting for the 2nd array.
> I need to come up with the most efficient solution with respect to time.

Yes, you have the right idea for the most efficient solution.

a. find n largest elements from the initial array - introselect O(n) O(sz) https://en.wikipedia.org/wiki/Introselect

b. copy these elements to second array. O(n)

c. use heap sorting for the 2nd array O( n log n )


A refinement that can be made is to eliminate the need for a second array:
a. partition the initial array to get the largest n elements into one partition O(n) O(sz)
b. sort the partion containing the largest elements in descending order O(n log n)


> i am not allowed to use third party libraries

The standard C++ library is not a 'third party' library (though you may be required to implement your own selection and sort algorithms). The simple partial selection sort may be all that is expected. https://en.wikipedia.org/wiki/Selection_algorithm#Partial_selection_sort

This is the general idea:

// partition the numbers into two parts: the largest 'N' numbers being the first part O(N) O(SZ)
// http://en.cppreference.com/w/cpp/algorithm/nth_element
std::nth_element( std::begin(numbers), std::begin(numbers)+N, std::end(numbers), std::greater<>{} ) ;

// sort these largest 'N' numbers in descending order O( N log N )
std::sort( std::begin(numbers), std::begin(numbers)+N, std::greater<>{} );

http://coliru.stacked-crooked.com/a/a7f99654ad67d0fe

[nlstmn]

gunnerfunner,
with iterators solution is obviosly simpler, but I am not allowed to use third party libraries

[JLBorges]

Partial selection sort (descending order):

void swap_values_at( int* array, std::size_t a, std::size_t b )
{
    const int temp = array[a] ;
    array[a] = array[b] ;
    array[b] = temp ;
}

// partially sort array 'arr' containing 'array_sz' elements so that the largest 'n' elements
// in descending order are brought to the first 'n' positions in the array   
void partial_sort_n( int* arr, std::size_t array_sz, std::size_t n ) // O( n * sz )
{
    for( std::size_t i = 0 ; i < n ; ++i )
    {
        std::size_t max_pos = i ;

        for( std::size_t j = i+1 ; j < array_sz ; ++j )
            if( arr[j] > arr[max_pos] ) max_pos = j ;

        swap_values_at( arr, i, max_pos ) ;
    }
}

"Look, career teacher - no 'third-party' libraries!" version:
http://coliru.stacked-crooked.com/a/140c7fbf74b6799f

Note: using std::set - or, to be correct, std::multiset - would be horrendously slower unless 'array_sz' is comparable to 'n'

[gunnerfunner]

OP: iterators is very much a part of the standard library (#include <iterators>) but, that said, JLBorges' solution is undoubtedly faster