Быстрый алгоритм выбора

Question

Я пытаюсь реализовать алгоритм быстрого выбора на массиве, который имеет случайно сгенерированные числа. Теперь, после написания алгоритма в коде, он не сортирует массив от самого низкого до самого высокого, и я не могу найти k-й наименьший элемент. Буду признателен за помощь. Спасибо.

#include<iostream> 
#include<ctime> 
#include<cstdlib> 
using namespace std; 

void printArray(int *myArray, int n){ 
    for(int i = 0; i < n; i++){ 
     cout << myArray[i] << " "; 
} 
} 

int Partition(int *myArray, int startingIndex, int endingIndex){ 
int pivot = myArray[endingIndex]; 
int partitionIndex = startingIndex; 
for(int i = startingIndex; i<endingIndex; i++){ 
    if(myArray[i]<= pivot){ 
     swap(myArray[i],myArray[partitionIndex]); 
     partitionIndex++; 
    } 
} 
swap(myArray[partitionIndex],myArray[endingIndex]); 
return partitionIndex; 
} 

int QuickSelect(int *myArray, int startingIndex, int endingIndex, int KthElement){ 
/*if(startingIndex < endingIndex){ 
    int partitionIndex = Partition(myArray, startingIndex,endingIndex); 
    QuickSelect(myArray,startingIndex,partitionIndex-1); 
    QuickSelect(myArray,partitionIndex+1,endingIndex); 
}*/1 
if (startingIndex < endingIndex){ 
    int partitionIndex = Partition(myArray, startingIndex, endingIndex); 
    if(KthElement == partitionIndex) 
     return KthElement; 
    if(KthElement < partitionIndex) 
     QuickSelect(myArray, startingIndex, partitionIndex - 1, KthElement); 
    else 
     QuickSelect(myArray, partitionIndex + 1, endingIndex, KthElement); 
} 
} 
int main(){ 

int numOfElements; 
int KthElement; 
srand(time(NULL)); 
cout<<"Enter The Amount Of Numbers You Wish To Use: "; 
cin >> numOfElements; 
int myArray[numOfElements]; 

cout << "Array Before Sorting: "; 
for(int i = 0; i< numOfElements; i++){ 
    myArray[i] = rand() %10; 
} 

printArray(myArray, numOfElements); 

cout << endl; 
cout << endl; 

cout <<"Enter The Index Of The Kth Element You Wish To Retrieve: "; 
cin >> KthElement; 

QuickSelect(myArray, 0,numOfElements,KthElement); 
cout << "Array After Sorting: "; 
printArray(myArray, numOfElements); 
cout << endl; 

cout <<"The " <<KthElement<<" Smallest Element Is: " << QuickSelect(myArray,0,numOfElements,KthElement); 

} 

Answer 1

Для numOfElements как 5, массив простирается от 0 до 4. Ваш endingIndex предполагает, что его последний индекс массива.

Fix:

QuickSelect(myArray, 0,numOfElements-1,KthElement); 

Проблемы с кодом:

• Ваша программа получает доступ из связанных местоположений массива в

  int pivot = myArray[endingIndex]; 
  

• Есть чек на k<1 и k>(num_of_elements).

• Проверьте свой код для num_of_elements = 1.

• Проверьте, что означает k для массива, т.е. для k=1, arr[0] необходимо вернуть не arr[1];