2020年12月21日星期一

Return the k-th smallest value of the array C++

I need to return the k-th smallest value of an array. I'm trying to use the quickselect algorithm to run the function. I know there's a lot of links on quickselect but the way my functions are setup are different and the way they are setup is how I need to use them. I don't have left, or right in my functions parameters. My question is, how do I get the find function to return the k-th smallest value in the array. 1 my first return doesn't get called and I don't know why. 2 I'm getting stack overflow with the else satement.

template <typename T>  void swap(T &i, T &j) {    T k = i;    i = j;    j = k;  }    template <typename T>  int partition(T* a, int length) {    int lo = 0, hi = length-1;    T pivot = a[0];    do {      while (lo <= hi && a[lo] <= pivot)        lo++;      while (a[hi] > pivot)        hi--;      if (lo < hi)        swap(a[lo],a[hi]);    } while (lo < hi);    swap(a[0],a[hi]);    return lo;  }  

The file with my code

template <typename T>  T find(T* a, int length, int k) {  // My code is here until the second return      int pivot = partition(a, length);            if (k == pivot) return a[pivot-1];            if (k < pivot) {          find(a, pivot - 1, k);      } else {          find(a, k - pivot, k);      }    return a[0];  }  

main.cpp

int length = 5;  int array[5] = {5,1,4,3,2};  std::cout << "array: [5,1,4,3,2]" << std::endl;  std::cout << "find 1st: " << find(array,length,1) << std::endl;  std::cout << "find 2nd: " << find(array,length,2) << std::endl;  std::cout << "find 3rd: " << find(array,length,3) << std::endl;  std::cout << "find 4th: " << find(array,length,4) << std::endl;  std::cout << "find 5th: " << find(array,length,5) << std::endl;  
https://stackoverflow.com/questions/65403053/return-the-k-th-smallest-value-of-the-array-c December 22, 2020 at 11:53AM

没有评论:

发表评论