Finding median of a list using quick select and median-of-medians

Question

Suppose A = [1, 2, 3, 4, 5, 6, 7, 8, 9]. I have to find the median here which is 5 and I am required to use the concept of quick select and median-of-medians. I have made the following code but for some reason, it outputs 4 which is wrong. Where could I have gone wrong?

The following are just some auxiliary functions needed for the latter functions.

int quick_select(int A[], int p, int r, int k);

void swapElements(int* i, int* j)
{
    int temp;
    temp = *i;
    *i = *j;
    *j = temp;
}
void insertion_sort(int A[], int from, int to)
{
    for(int i = from; i < to; i++) {
        for(int j = i + 1; j > from && A[j] < A[j - 1]; j--) {
            int temp = A[j - 1];
            A[j - 1] = A[j];
            A[j] = temp;
        }
    }
}

For the following, I made the code for median-of-medians. What this does is that it partitions the whole array into groups of 5 elements and at most 1 group containing less than 5 elements.

int median_of_medians(int A[], int p, int r){
    int N = (r-p)+1;
    int numberOfGroups = ceil((double)N/(double)5);
    int groupsOf5 = floor((double)N/(double)5);
    int lessThan5 = numberOfGroups - groupsOf5;
    int *arrayofMedians = (int*)malloc(numberOfGroups*sizeof(int));
    int rank = floor(((double)N+(double)1)/(double)2); //floor((N+1)/2)

    //sort each groups
    if(N>=5)
    {
        int ctrLeft = 0, ctrRight = 4;
        for(int j=1; j<=numberOfGroups;j++)
        {
            insertion_sort(A,ctrLeft,ctrRight);
            if(j<groupsOf5)
            {
                ctrLeft = ctrLeft + 5;
                ctrRight = ctrRight + 5;
            }
            else if(lessThan5>0)
            {
                ctrLeft = ctrRight + 1;
                ctrRight = N-1; //ctrRight+1+((N-1)%5);
            }

        }
    }
    else if(lessThan5!=0)
    {
        int ctrLeft = 0, ctrRight = N-1;
        insertion_sort(A, ctrLeft, ctrRight);

    }

    //find median from each group then put each median to arrayofMedians
    int ctr = 0;
    for(int j=0; j<numberOfGroups; j++)
    {
        if(j<groupsOf5)
        {
            arrayofMedians[ctr] = A[2+(j*5)];
            ctr++;
        }
        else
        {
            int rem = N % 5;
            if((rem % 2)==0) //if even
            {
                arrayofMedians[ctr] = A[(5*groupsOf5) + ((rem/2) - 1)];
            }
            else //if odd
            {
                arrayofMedians[ctr] = A[(5*groupsOf5) + (((rem+1)/2)-1)];
            }
            ctr++;
        }

    }

    //for(int i=0; i<=numberOfGroups-1; i++)
        //printf("%d ", arrayofMedians[i]);
    //Find median from arrayofMedians

    int finalMedian = quick_select(arrayofMedians, 0, numberOfGroups-1,rank);

    return finalMedian;
}

This is now the part where it partitions the array using the median found in median-of-medians

int median_partition(int A[], int p, int r){
    int median = median_of_medians(A, p, r);
    //find index ind of median
    int ind;
    for(int j=p; j<=r; j++)
    {
        if(A[j]==median)
            ind = j; //we found the index
    }

    swapElements(A+ind, A+r); //then swap A[ind] with A[r]


    int x = A[r];
    int i = p-1;
    for(int j=p; j<=r-1; j++)
    {
        if(A[j]<=x)
        {
            i++;
            swapElements(A+i, A+j);
        }
    }
    swapElements(A+(i+1), A+r);
    return(i+1);
}

This is the function for quick_select

int quick_select(int A[], int p, int r, int rank){
    if(p==r)
        return A[p];
    int q = median_partition(A, p, r); //median_partition(A, p, r)
    int k = q-p+1;
    if(rank==k)
        return A[q];
    else if(rank<k)
        return quick_select(A, p, q-1, rank);
    else
        return quick_select(A, q+1, r, rank-k);
}

this is the function for the main()

int main(){
    int T, M, *arr;
    scanf("%d", &T);
    while(T > 0){
        scanf("%d", &M);
        arr = (int*)malloc(M*sizeof(int));

        //read the elements of the input array
        for(int i=0; i<M; i++){
            scanf("%d",&arr[i]);
        }

        int median_index = ((M+1)/2);
        printf("Median: %d\n", quick_select(arr, 0, M-1, median_index));
        T--;
    }
}

Answer 1

    int finalMedian = quick_select(arrayofMedians, 0, numberOfGroups-1,rank);

Here rank is wrong - it is set to the middle of array A, but should rather be the middle of array arrayofMedians. Change to:

    int finalMedian = quick_select(arrayofMedians, 0, numberOfGroups-1, ctr/2);

Also in the function int median_of_medians(int A[], int p, int r) you're indexing array A always from index 0 on, while indexing should rather start at p. To correct this, insert A += p; near the start of the function.