CODEWITHSUNDEEP
calgorithmquicksort
user3589951
user3589951

Reputation: 13

Quicksort algorithm in-place crashes after some iterations

I have implemented the following quicksort algorithm to sort couples of points(3D space). Every couple defines a line: the purpose is to place all lines that have a distance less or equal to powR nearby inside the array which contains all the couples. The Array containing coordinates is monodimentional, every 6 elements define a couple and every 3 a point.

When i run the algorithm with an array of 3099642 elements stops after processing 2799222 trying to enter the next iteration. if i start the algorithm from element 2799228 it stops at 3066300. I can't figure out where is the problem, and suggestion?

void QuickSort(float *array, int from, int to, float powR){

float pivot[6];
float temp[6];

float x1;
float y1;
float z1;
float x2;
float y2;
float z2;
float d12;

int i;
int j;

if(from >= to)
    return;

pivot[0] = array[from+0];
pivot[1] = array[from+1];
pivot[2] = array[from+2];
pivot[3] = array[from+3];
pivot[4] = array[from+4];
pivot[5] = array[from+5];

i = from;

for(j = from+6; j <= to; j += 6){

    x1 = pivot[0] - array[j+0];
    y1 = pivot[1] - array[j+1];
    z1 = pivot[2] - array[j+2];
    x2 = pivot[3] - array[j+3];
    y2 = pivot[4] - array[j+4];
    z2 = pivot[5] - array[j+5];
    d12 = (x1*x1 + y1*y1 + z1*z1) + (x2*x2 + y2*y2 + z2*z2);
/*the sorting condition i am using is the regular euclidean norm*/
    if (d12 <= powR){
                i += 6;

                temp[0] = array[i+0];
                temp[1] = array[i+1];
                temp[2] = array[i+2];
                temp[3] = array[i+3];
                temp[4] = array[i+4];
                temp[5] = array[i+5];

                array[i+0] = array[j+0];
                array[i+1] = array[j+1];
                array[i+2] = array[j+2];
                array[i+3] = array[j+3];
                array[i+4] = array[j+4];
                array[i+5] = array[j+5];

                array[j+0] = temp[0];
                array[j+1] = temp[1];
                array[j+2] = temp[2];
                array[j+3] = temp[3];
                array[j+4] = temp[4];
                array[j+5] = temp[5];
    }
}

QuickSort(array, i+6, to, powR);
}

function is called in this way: float LORs = (float) calloc((unsigned)tot, sizeof(float));

LORs is filled reading datas from a file, and works fine.

QuickSort(LORs, 0, 6000, powR);

    free(LORs);

Upvotes: 1

Views: 95

Answers (1)

gsamaras
gsamaras

Reputation: 73366

for(j = from+6; j <= to; j += 6) {
    array[i+0] = array[j+0];
    array[i+1] = array[j+1];
    array[i+2] = array[j+2];
    array[i+3] = array[j+3];
    array[i+4] = array[j+4];
    array[i+5] = array[j+5];
}

Your j + constant_number goes out of bounds when you approach the end. That's why it crashes at the end. Note that constant_number is non-negative.

When j comes close (how close you can find by the increment step, i.e. +6) to the end of your array, it will go for sure out of bounds.

Take the easy case, the max value j can get. That is the size of your array. So, let's call it N.

Then, when j is equal to N, you are going to enter the loop.

Then, you want to access array[j + 0], which is actually array[N + 0], which is array[N].

I am pretty sure, you know that indexing in C (which you should in the future include in the tags of your questions is needed), is from 0 to N - 1. And so on..

EDIT: As the comments suggest, this is not a (quick)sort!

I had implemented quickSort here, is you want to take an idea of it. I suggest you start from the explanations and not from the code!

Upvotes: 1

Related Questions