BFPRT (median of medians) algorithm crashes after 185000 array

0

My BFPRT algorithm crashes as soon as I put a 1300.000 int size array but it works perfectly fine below that. I know that probably it's a memory allocation problem but I have been struggling for days and didn't get to an answer.
I think I allocated my array to the heap so this should'nt be a stack overflow right? Do you think replacing my array with a vector will solve the issue? I tried it but didn't quite get it to work. (vectors are really conusing to me atm)

My debugger says :

>Program received signal SIGSEGV, Segmentation fault.  
>In ?? () ()

>[debug]> bt 30  
>[debug]#0  0x0000002b in ?? ()  
>[debug]Backtrace stopped: Cannot access memory at address 0x0  
>[debug]>>>>>>cb_gdb:  

Any help would be gratefull This is my code:

#include <iostream>
#include <math.h>
#include <random>
#include <chrono>
#include <fstream>
#include <algorithm>
#include <stdint.h>

using namespace std;

int32_t ithSmallest(int32_t arr[],int32_t low, int32_t high, int32_t iosto);

//sinartisi poy ftiaxnei ton pinaka
void arrayMaker (){
        int32_t n = 185000;
        int32_t *values = new int32_t[n];


        //apotelesmata simfwna me omoiomorfh katanomh
        std::random_device                  rand_dev;
        std::mt19937                        generator(rand_dev());
        std::uniform_int_distribution<int64_t>  unif(1,pow(10,10));

        for (int32_t i = 0; i < n; i++){
            values[i] = unif(generator);
        }

        ithSmallest(values,0,n-1,2);

        delete[] values;
}

int32_t vresMeso(int32_t arr[],int32_t n){
    sort (arr, arr+n);
    return arr[n/2];
}

int32_t partitionise(int32_t arr[], int32_t l, int32_t r, int32_t x)
{
    // Search for x in arr[l..r] and move it to end
    int32_t i;
    for (i=l; i<r; i++)
        if (arr[i] == x)
           break;
    swap(&arr[i], &arr[r]);

    // Standard partition algorithm
    i = l;
    for (int32_t j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x)
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]);
    return i;
}

//Xeiroterhs periptwshs
int32_t ithSmallest(int32_t arr[],int32_t low, int32_t high, int32_t iosto){

    //an to noymero poy psaxnoyme yparxei kapoy mesa ston pinaka
    if (iosto > 0 && iosto <= high-low+1){
        //plithos stoixeiwn pinaka
        int32_t n = high - low + 1;
        //max (n+4)/5 group
        int32_t median[(n+4)/5];
        int32_t i;
        //Ftiaxe ta groupakia
        for (i=0; i<n/5; i++){
            median[i] = vresMeso(arr+low+i*5, 5);
            //cout << "gamw " << median[i] << endl;
        }
        //Gia to teleytaio groupaki an exei ligotera stoixeia
        if (n%5 != 0)
        {
            median[i] = vresMeso(arr+low+i*5, n%5);
            i++;
        }
        /*for (int32_t b = 0; b < i; b++){
                cout << "mediansPrwta = " << median[b] << endl;
        }*/


        //Vres ton meso twn meso me anadromh
        //Ama exeis 1 stoixeio mhn kaneis anadromh
        int32_t medOfMed = (i == 1)? median[i-1]:
                                 ithSmallest(median, 0, i-1, i/2);


        int32_t pos = partitionise(arr, low, high, medOfMed);

        // If position is same as k
        if (pos-low == iosto - 1)
            return arr[pos];
        if (pos-low > iosto - 1)  // If position is more, recur for left
            return ithSmallest(arr, low, pos-1, iosto);

        // Else recur for right subarray
        return ithSmallest(arr, pos+1, high, iosto-pos+low-1);
    }

    // If k is more than number of elements in array
    return INT_MAX;

}

int main()
{
    arrayMaker();
}
c++
algorithm
sorting
memory

1 Answer

0

Try:

int32_t n = 185000;
double *values = new int32_t[n];

...

delete[] values;

or

int32_t n = 185000;
std::vector<int32_t> values;

Also this:

std::uniform_int_distribution<int32_t>  unif(1,pow(10,10));

looks bad, because that pow is a poorly-described magic number. Maybe you meant this...

#include <limits>
std::uniform_int_distribution<int32_t>  unif(1,std::numeric_limits<int32_t>::max());
answered on Stack Overflow Mar 3, 2019 by Richard

User contributions licensed under CC BY-SA 3.0