Smallest kth for quick select algor

1
votes

I've been working on a program that is supposed to test the performance of quick select algorithm under different group size setting. You find the pivot, the algorithm will divide all the elements into group of 5. Its supposed to find the median of each group and use the median of medians from all group as pivot. I'm having an issue with the smallest kth part. The errors that I'm getting is that n is not a constant variable so it cannot allocate the array and that it causes median to have an unknown size. What should I do to correct this? 

int smallestKth(int ray[], int l, int r, int k)

 {
if (k > 0 && k <= r - l + 1)

{

    int n = r-l+1; 
    int i, median[(n+4)/5]; 
    for (i=0; i<n/5; i++)
        median[i] = medianFind(ray+l+i*5, 5);
    if (i*5 < n) 

    {
        median[i] = medianFind(ray+l+i*5, n%5);
        i++;
    }   


    int medOfMed = (i == 1)? median[i-1]:
        smallestKth(median, 0, i-1, i/2);


    int pivotPosition = part(ray, l, r, medOfMed);
    if (pivotPosition-l == k-1)
        return ray[pivotPosition];

    if (pivotPosition-l > k-1) 
        return smallestKth(ray, l, pivotPosition-1, k);      
    return smallestKth(ray, pivotPosition+1, r, k-pivotPosition+l-1);

}
return INT_MAX;

}
3
c++algorithm

3 Answers

2
votes

int median[(n+4)/5]; is a nonstandard declaration supported by some compilers as an extension. Rather than using a Variable Length Array (VLA), you should use std::vector.

std::vector median((n+4)/5);
1
votes

You don't need to make a new array to hold the medians. Just use a fifth of the original array.

One way to do that is to stride the array; represent the array as a starting pointer, a number of elements, and a stride, which is the distance between two consecutive elements. For example, once you've finished putting tbe median of each group of five in the right place in the array [start, n, stride], you can recurse on the array [start+2, (n+2)/5, 5*stride].

0
votes

This was solved by creating a pointer for the median array.

int n = right-left+1;
    int *median = new int[(n+4)/5];