K-ое наибольшее число в массиве с использованием алгоритма "Sort K number of elements array"

Question

Я пытаюсь реализовать следующий алгоритм, чтобы найти k-е наибольшее количество входных данных в текстовом файле. Первое число определяет переменную k, следующее число определяет общее количество элементов (N), а остальные - список номеров. Описание алгоритма:

• Хранить только первые k чисел в массиве
• Сортировать массив в порядке убывания, например, используя сортировку вставок
• Прочитать остальныеиз чисел одно за другим:
• Игнорировать, если оно меньше числа в k-й позиции в массиве
• В противном случае;вставьте его в правильную позицию в массиве и сдвиньте оставшиеся числа (число в k-й позиции будет выброшено из массива)
• Возвращает число с индексом k-1 в массиве.

AlgorithmSortK::AlgorithmSortK(int k) : SelectionAlgorithm(k)
{
    this->k = k;

}



int AlgorithmSortK::select()
{

    int N = 0;
    int x=0;
    int *pNums = 0;
    cin>>N;
    cout<<"N:"<<N<<endl;
    pNums = new int[N];
     int key, j;
    for (int i=0; i<k; i++)
    {
        cin>>x;
        pNums[i] = x;
        cout<<pNums[i]<<endl;



        for (i = 1; i <k; i++)
        {
            key = pNums[i];
            j = i - 1;
            while (j >= 0 && pNums[j] <key)
            {
                pNums[j + 1] = pNums[j];
                j = j - 1;
            }
            pNums[j + 1] = key;
        }

        for ( i=k; i<N; i++)
        {
            cin>>x;

            if(x>pNums[k-1])
            {

                for (int shifter=0; shifter<k; shifter++)
                {
                    pNums[shifter]=x;

                    pNums[shifter] =  pNums[shifter+1];

                }
                for (int r = 1; r <k; r++)
                {

                    key = pNums[r];
                    j = r - 1;
                    while (j >= 0 && pNums[j] <key)
                    {
                        pNums[j + 1] = pNums[j];
                        j = j - 1;
                    }
                    pNums[j + 1] = key;

                }
            }
        }
        cout<<"pNums[k-1]:"<<pNums[k-1]<<endl;
    }

Это мой код, он корректно компилируется, но я получил другой и неправильный результат для pNums [k-1]. Я думаю, что я делаю сдвиг и удаление элемента при индексных операциях k-1 неправильно. N - общее количество элементов, и я использую сортировку вставок для массива с ограничением k.

Answer 1

Это должно помочь:

int AlgorithmSortK::select()
{
    int N, x;

    cin >> N;    // number of the input elements
    cout << "N:" << N << endl;

    std::vector<int> nums;
    nums.resize( k, std::numeric_limits<int>::min() );    // assume 'k' is defined elsewhere

    for(int i=0; i<N; i++)
    {
        cin >> x;  // get the next element

        // shift it down while it's larger than existing numbers
        for( int j=0; j<k; j++) {
            if( x > nums[j] ) {
                std::swap( x, nums[j] );
            }
        }
    }
    cout<<"nums[k-1]:" << nums[k-1]<<endl;
}

Сложность O(N*k), может сделать это быстрее, но я бы предпочел, чтобы это было проще.