0

ランダムに生成された数値を持つ配列にクイック選択アルゴリズムを実装しようとしています。アルゴリズムをコードで記述した後、配列を最小から最大にソートせず、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);

}
4

1 に答える 1

2

as 5 の場合numOfElements、配列は 0 から 4 まで拡張されますendingIndex。配列の最後のインデックスであると仮定します。

修理：

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

コードの問題:

  • あなたのプログラムは、範囲外の配列の場所にアクセスします

    int pivot = myArray[endingIndex];

  • k<1とにチェックを入れk>(num_of_elements)ます。

  • num_of_elements = 1 のコードも確認してください。

  • 配列に対する k の意味を確認してください。つまり、 Fork=1はarr[0]not を返す必要がありarr[1]ます。

于 2015-01-07T07:38:23.677 に答える