Реализация QuickSelect на C++ без дополнительного распределения памяти

Question

У меня есть небольшая помощь по дому, если вы не возражаете. В основном идея состоит в том, чтобы выполнить quickselect в массиве значений, однако нам был предоставлен шаблон, и я не могу понять, как заставить функции работать с тем, что предоставляется.

Проблема заключается в том, что значения не будут упорядочиваться должным образом, или если они это сделают, они будут меняться каждый раз, когда вводится одно и то же значение.

Вот функции, с которыми я работаю, я буду обозначать код, который я написал с помощью/**/после кода, и любая другая строка является частью шаблона, который был предоставлен для меня.

#include <iostream> 
#include <fstream> 
#include <cstdlib> 
#include <algorithm> 

using namespace std; 

int partition(int *A, int len, int pivot_index) 
{ 
    int pivot_value = A[pivot_index]; /**/ 

    int left = 0; /**/ 
    int l = left; /**/ 
    int right = len - 1; /**/ 
    while(left < right) /**/ 
    { /**/ 
     while(A[left] < pivot_value) /**/ 
     { /**/ 
     left++; /**/ 
     } /**/ 

     while(A[right] > pivot_value) /**/ 
     { /**/ 
     right--; /**/ 
     } /**/ 

     if(A[left] < pivot_value) /**/ 
     { /**/ 
     swap(A[left], A[right]); /**/ 
     } /**/ 
    } /**/ 

    return left; /**/ 
} 


int select (int *A, int len, int rank) 
{ 
     if (len==1) return A[0]; 
     int pivot_index = rand() % len; 
     int pivot_rank = partition(A, len, pivot_index); 

     if (rank == pivot_rank) return A[rank]; 
     if (rank < pivot_rank) return select(A, pivot_rank, rank); 
     return select(A, len - pivot_rank, rank - pivot_rank); /**/ 
} 

int main(void) 
{ 
    int N, *A; 

    ifstream fin("test.txt"); 
    fin >> N; 
    A = new int[N]; 
    for (int i=0; i<N; i++) fin >> A[i]; 
    fin.close(); 

    int r; 
    cout << "Enter rank (0.." << N-1 << ")\n"; 
    while (cin >> r) { 
     if (r < 0 || r >= N) 
     cout << "Invalid rank\n"; 
    else 
     cout << "The element of rank " << r << " is " << select(A,N,r) << "\n"; 
    } 

    delete[] A; 
} 

Мой файл «test.txt» содержит следующие значения:

10 -- this denotes the length of the array or how many values it will read in 
7 
14 
12 
2 
25 
18 
15 
13 
100 
63 

Любая помощь с этим было бы весьма признателен .. мой профессор не объяснил, как это будет работать на всех, и любой другой примеры, которые я нашел в Интернете, не отвечают на мой вопрос. Я провел много часов, играя с разными способами реализации этого, и на данный момент я просто понятия не имею. Спасибо

EDIT: изменено так, что теперь можно непосредственно реализовать и скомпилировать. Также добавлены библиотеки, которые я использую.

Answer 1

В вашем коде есть множество проблем.

while(A[left] < pivot_value) { left++; } 

Это не проверяет, что левое не выходит за пределы массива.

while(A[right] > pivot_value) { right--;} 

Это не проверяет, что это право не запускается до начала массива.

while(left < right) 

Это бесконечный цикл, когда

1. покинул < правый
2. A [левый]> = pivot_value
3. A [вправо] < = pivot_value

select(A, len - pivot_rank, rank - pivot_rank);

Это не правильный раздел для продолжения.