sorting an array of pointers according to the integers value

Question

I got this as homework. using merge-sort, I'm trying to sort an array of integers that a new array of pointers will hold the pointers to each integer in the right order so if arr = {7,2,5,9,4} than the pointers array will be {ptr to 2, ptr to 4, ptr to 5, ptr to 7, ptr to 9}

so, at first I was required to write the function as following:

int** pointerSort(int* arr, int size);

and I did that:

int** pointerSort(int* arr, int size) {
int **res1, **res2, **res;
if (size <= 1) {
    if (size == 0)
        return NULL;

    res = (int **)malloc(sizeof(int) * size);
    *res = arr;

    return res;
}

res1 = pointerSort(arr, size/2);
res2 = pointerSort(arr + size/2, size - size/2);

res = (int **)malloc(sizeof(int **) * size);
merge(res1,size/2,res2, size - size/2,res);

return res;
}


void merge (int **arr1, int size1, int **arr2, int size2, int **res) {

int i1,i2, resI;
i1 = i2 = resI = 0;

while (i1 < size1 && i2 < size2) {
    if (**(arr1 + i1) <= **(arr2 + i2)){
        *(res + resI++) = *(arr1 + i1++);
    }
    else {
        *(res + resI++) = *(arr2 + i2++);
    }
}
while (i1 < size1) {
    *(res + resI++) = *(arr1 + i1++);
}

while (i2 < size2) {
    *(res + resI++) = *(arr2 + i2++);
}
}

but after that I needed to change it to

void pointerSort2(int* arr, int size, int*** pointers);

and that's where I'm stuck. This is what I've got so far and it doesn't seem to work

void pointerSort2(int* arr, int size, int*** pointers) {
    if (size <= 1) {
        if (size == 0)
            return;

        pointers = (int ***)malloc(size * sizeof(int ***));
        *pointers = &arr;

        return;
    }
    pointerSort2(arr, size/2,pointers);
    pointerSort2(arr + size/2, size - size/2,pointers);

    int ***res = (int ***)malloc(sizeof(int ***) * size);
    merge2(pointers,size/2,pointers, size - size/2,res);

    pointers = res;
}

void merge2 (int ***arr1, int size1, int ***arr2, int size2, int ***res) {
    int i1,i2, resI;
    i1 = i2 = resI = 0;
    int val;
    int val2;
    int b;
    while (i1 < size1 && i2 < size2) {
            int val = ***(arr1 + i1);
    int val2 = ***(arr2 + i2);
    int b = ***(arr1 + i1) <= ***(arr2 + i2);
        if (b) {
            *(res + resI++) = *(arr1 + i1++);
        }
        else {
            *(res + resI++) = *(arr2 + i2++);
        }
    }
    while (i1 < size1) {
        *(res + resI++) = *(arr1 + i1++);
    }

    while (i2 < size2) {
        *(res + resI++) = *(arr2 + i2++);
    }
}

Thanks a lot

There is no question here. "after that I needed to change it to" and "that's where I'm stuck" do not form anything comprehensible. Clearly state the requirements and how did you try to fulfill them and what went wrong. — SomeWittyUsername
– SomeWittyUsername, Commented Apr 1, 2013 at 8:58
From a brief look you have allocation mistakes in both of your versions. malloc works this way: Type* res = malloc(sizeof(Type) * size); - mind the correctness of dereferences. — SomeWittyUsername
– SomeWittyUsername, Commented Apr 1, 2013 at 9:00
Do some work on this code, and then put only the doubtful code where you may find some problem. To put all the code is not right way to ask the question. So, for quick and better solution, put your actual problem rather then whole code. Please refer it this article — AB Bolim
– AB Bolim, Commented Apr 1, 2013 at 9:02
icepack3, there is a question here - the requirements were that I take pointerSort function and change it's signature so that int ***pointers holds what pointerSort returned originally. and While doing that I got stuck - and the code is below — Tomer Gal
– Tomer Gal, Commented Apr 1, 2013 at 9:03

MOHAMED · Accepted Answer · 2013-04-01 10:29:06Z

First of all I have 2 remarks for you concerning the first function pointerSort()

1) replace the allocation of res

res = (int **)malloc(sizeof(int) * size);
res = (int **)malloc(sizeof(int**) * size);

with only

res = (int **)malloc(sizeof(int *) * size);

2) add free for res1 and res2 after the merge otherwise you will get a memory leak

res = (int **)malloc(sizeof(int **) * size);
merge(res1,size/2,res2, size - size/2,res);
free(res1);
free(res2);

Concerning your functions pointerSort2 and merge2 : there is many code errors in both function. here after the new code fixed.

Note: Playing with multi level pointer is some thing complicated. be careful when use it

void pointerSort2(int* arr, int size, int*** pointers) {
    int **tmp;
    int **pointers1, **pointers2;
    if (size <= 1) {
        if (size == 0)
            return;

        tmp = (int **)malloc(size * sizeof(int **));
        *tmp = arr;
        *pointers = tmp;
        return;
    }
    pointerSort2(arr, size/2,&pointers1);
    pointerSort2(arr + size/2, size - size/2,&pointers2);


    merge2(pointers1,size/2,pointers2, size - size/2,&tmp);
    free(pointers1);
    free(pointers2);    
    *pointers = tmp;
}

void merge2 (int **arr1, int size1, int **arr2, int size2, int ***res) {
    int i1,i2, resI;
    i1 = i2 = resI = 0;
    int val;
    int val2;
    int b;
    int **tmp = (int **)malloc((size1+size2) * sizeof(int **));
    *res = tmp;
    while (i1 < size1 && i2 < size2) {
            int val = **(arr1 + i1);
    int val2 = **(arr2 + i2);
    int b = **(arr1 + i1) <= **(arr2 + i2);
        if (b) {
            *(tmp + resI++) = *(arr1 + i1++);
        }
        else {
            *(tmp + resI++) = *(arr2 + i2++);
        }
    }
    while (i1 < size1) {
        *(tmp + resI++) = *(arr1 + i1++);
    }

    while (i2 < size2) {
        *(tmp + resI++) = *(arr2 + i2++);
    }
}

The call of pointerSort2 in the main should be

int arr[5] = {2, 5, 3, 7, 6}
int **res;
pointerSort2(arr, 5, &res);

@TomerGal Answer updated. it contains the code fixed of both function pointerSort2 and merge2

Collectives™ on Stack Overflow

sorting an array of pointers according to the integers value

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related