빠른 선택 알고리즘

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

5로 numOfElements를 들어, 배열이 4 0에서 endingIndex가 가정 나오 배열의 마지막 인덱스입니다.

수정 : 코드와

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]이 아닌 것으로 반환됩니다.