Error median media?

Question

What i understand already

I understand that the median of the median algorithm (I will denote it as MoM) is an algorithm with a high constant coefficient O (N). He finds the medians of k-groups (usually 5) and uses them as the next set of iterations to search for medians. After finding this value, the drill will be between 3 / 10n and 7 / 10n of the original set, where n is the number of iterations that were required to find one middle base case.

I keep getting segmentation error when I run this code for MoM, but I'm not sure why. I debugged this and I think the problem is what I'm calling medianOfMedian(medians, 0, medians.size()-1, medians.size()/2);. However, I thought it was logically great, since we had to recursively find the median by calling ourselves. Perhaps my base case is wrong? In the YogiBearian textbook on youtube (Stanford professor, link: https://www.youtube.com/watch?v=YU1HfMiJzwg ), he did not indicate any additional base case to take care of the O (N / 5) recursion operation in MoM.

Full code

Note. In the sentences, I added a basic example and used the .at () function with vectors.

static const int GROUP_SIZE = 5;
/* Helper function for m of m. This function divides the array into chunks of 5 
 * and finds the median of each group and puts it into a vector to return.
 * The last group will be sorted and the median will be found despite its uneven size.
 */
vector<int> findMedians(vector<int>& vec, int start, int end){
    vector<int> medians;
    for(int i = start; i <= end; i+= GROUP_SIZE){
        std::sort(vec.begin()+i, min(vec.begin()+i+GROUP_SIZE, vec.end()));
        medians.push_back(vec.at(min(i + (GROUP_SIZE/2), (i + end)/2)));
    }
    return medians;
}

/* Job is to partition the array into chunks of 5(subject to change via const)
 * And then find the median of them. Do this recursively using select as well.
 */
int medianOfMedian(vector<int>& vec, int start, int end, int k){
    /* Acquire the medians of the 5-groups */
    vector<int> medians = findMedians(vec, start, end);

    /* Find the median of this */
    int pivotVal;
    if(medians.size() == 1)
        pivotVal = medians.at(0);
    else
        pivotVal = medianOfMedian(medians, 0, medians.size()-1, medians.size()/2);

    /* Stealing a page from select() ... */
    int pivot = partitionHelper(vec, pivotVal, start, end);

    cout << "After pivoting with the value " << pivot << " we get : " << endl;
    for(int i = start; i < end; i++){
        cout << vec.at(i) << ", ";
    }
    cout << "\n\n" << endl;
    usleep(10000);
    int length = pivot - start + 1;
    if(k < length){
        return medianOfMedian(vec, k, start, pivot-1);
    }
    else if(k == length){
        return vec[k];
    }
    else{
        return medianOfMedian(vec, k-length, pivot+1, end);
    }

}

Some additional features to help unit test

Here are some unit tests that I wrote for these two functions. I hope they help.

vector<int> initialize(int size, int mod){
    int arr[size];
    for(int i = 0; i < size; i++){
    arr[i] = rand() % mod;
    }
    vector<int> vec(arr, arr+size);
    return vec;
}

/* Unit test for findMedians */
void testFindMedians(){
    const int SIZE = 36;
    const int MOD = 20;
    vector<int> vec = initialize(SIZE, MOD);
    for(int i = 0; i < SIZE; i++){
        cout << vec[i] << ", ";
    }
    cout << "\n\n" << endl;

    vector<int> medians = findMedians(vec, 0, SIZE-1);

    cout << "The 5-sorted version: " << endl;
    for(int i = 0; i < SIZE; i++){
        cout << vec[i] << ", ";
    }
    cout << "\n\n" << endl;

    cout << "The medians extracted: " << endl;
    for(int i = 0; i < medians.size(); i++){
        cout << medians[i] << ", ";
    }
    cout << "\n\n" << endl;
}

/* Unit test for medianOfMedian */
void testMedianOfMedian(){
    const int SIZE = 30;
    const int MOD = 70;
    vector<int> vec = initialize(SIZE, MOD);
    cout << "Given array : " << endl;
    for(int i = 0; i < SIZE; i++){
        cout << vec[i] << ", ";
    }
    cout << "\n\n" << endl;
    int median = medianOfMedian(vec, 0, vec.size()-1, vec.size()/2); 
    cout << "\n\nThe median is : " << median << endl;

    cout << "As opposed to sorting and then showing the median... : " << endl;
    std::sort(vec.begin(), vec.end());
    cout << "sorted array : " << endl;
    for(int i = 0; i < SIZE; i++){
        if(i == SIZE/2)
            cout << "**";
        cout << vec[i] << ", ";
    }
    cout << "Median : " << vec[SIZE/2] << endl;
}

,

Given array :
7, 49, 23, 48, 20, 62, 44, 8, 43, 29, 20, 65, 42, 62, 7, 33, 37, 39, 60, 52, 53, 19, 29, 7, 50, 3, 69, 58, 56, 65,

After pivoting with the value 5 we get :
23, 29, 39, 42, 43,

After pivoting with the value 0 we get :
39,

Segmentation Fault: 11

, , . , ( ).

: , , quickSelect .

, , MVCE, !

EDIT: , . , - , , 0 -1 , . .

Answer 1

MoM ( pivot) , , . " " : - " ", .

Answer 2

. , , , , :

• <= 5.

• , ( ) . , .

. - !

/* In case someone wants to pass in the pivValue, I broke partition into 2 pieces.
 */
int pivot(vector<int>& vec, int pivot, int start, int end){

    /* Now we need to go into the array with a starting left and right value. */
    int left = start, right = end-1;
    while(left < right){
        /* Increase the left and the right values until inappropriate value comes */
        while(vec.at(left) < pivot && left <= right) left++;
        while(vec.at(right) > pivot && right >= left) right--;

        /* In case of duplicate values, we must take care of this special case. */
        if(left >= right) break;
        else if(vec.at(left) == vec.at(right)){ left++; continue; }

        /* Do the normal swapping */
        int temp = vec.at(left);
        vec.at(left) = vec.at(right);
        vec.at(right) = temp;
    }
    return right;
}


/* Returns the k-th element of this array. */
int MoM(vector<int>& vec, int k, int start, int end){
    /* Start by base case: Sort if less than 10 size
     * E.x.: Size = 9, 9 - 0 = 9.
     */
    if(end-start < 10){
        sort(vec.begin()+start, vec.begin()+end);
        return vec.at(k);
    }

    vector<int> medians;
    /* Now sort every consecutive 5 */
    for(int i = start; i < end; i+=5){
        if(end - i < 10){
            sort(vec.begin()+i, vec.begin()+end);
            medians.push_back(vec.at((i+end)/2));
        }
        else{
            sort(vec.begin()+i, vec.begin()+i+5);
            medians.push_back(vec.at(i+2));
        }
    }

    int median = MoM(medians, medians.size()/2, 0, medians.size());

    /* use the median to pivot around */
    int piv = pivot(vec, median, start, end);
    int length = piv - start+1;

    if(k < length){
        return MoM(vec, k, start, piv);
    }
    else if(k > length){
        return MoM(vec, k-length, piv+1, end);
    }
    else
        return vec[k];
}