快速选择算法 [英] Quick Select Algorithm
问题描述
我正在尝试对随机生成数字的数组实施快速选择算法。现在,在用代码编写算法之后,它无法将数组从最低到最高排序,也无法找到第k个最小的元素。我会很感激我得到的帮助。谢谢。
Im trying to implement the Quick Select Algorithm on a Array that has randomly generated numbers. Now after writing the algorithm in code, it does not sort the array from lowest to highest nor am i able to find the kth smallest element. I would appreciate the help i get. Thank you.
#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);
}
推荐答案
对于 numOfElements
为5,数组从0扩展到4。
您的 endingIndex 假定其最后一个索引为
For numOfElements
as 5, array extends from 0 to 4.
Your endingIndex
assumes that its the last index of the array.
修复:
QuickSelect(myArray, 0,numOfElements-1,KthElement);
您的代码存在问题:
-
您的程序访问
Your program accesses out of bound array locations in
int pivot = myArray[endingIndex];
检查 k< 1
和 k>(num_of_elements)
。
还要检查代码中的num_of_elements = 1。
Check your code for num_of_elements = 1 as well.
检查k对数组的含义,即对于 k = 1
, arr [0]
不应返回 arr [1]
;
Check what k means for the array, i.e For k=1
, arr[0]
should be returned not arr[1]
;
这篇关于快速选择算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!