使用 quick select 和 median-of-medians 查找列表的中位数

Question

假设 A = [1, 2, 3, 4, 5, 6, 7, 8, 9]。我必须在这里找到中位数，即 5，我需要使用快速 select 和中位数中位数的概念。我制作了以下代码，但出于某种原因，它输出了 4，这是错误的。我哪里可能出错了？

以下只是后面功能需要的一些辅助功能

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;
        }
    }
}

对于以下内容，我编写了中位数的代码。这样做的目的是将整个数组分成 5 个元素的组，并且最多 1 个包含少于 5 个元素的组。

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;
}

这是现在使用中位数中位数对数组进行分区的部分

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);
}

这是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);
}

这是 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);

这里的 rank 是错误的 - 它设置在数组 A 的中间，但应该是数组 arrayofMedians 的中间。更改为：

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

同样在函数 int median_of_medians(int A[], int p, int r) 中，您总是从索引 0 开始索引数组 A，而索引应该从 p 开始。要更正此问题，请在函数开头附近插入 A += p;。

使用 quick select 和 median-of-medians 查找列表的中位数

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

c

median

median-of-medians

quickselect