Медиана медиан с использованием C приводит к ошибке сегментации - PullRequest
Новая
       31

Медиана медиан с использованием C приводит к ошибке сегментации

0 голосов
/ 14 сентября 2018 
#include<stdio.h>
#include<stdlib.h>

int partition(int a[],int f,int l,int x);
int medianOfmedians(int array[],int f,int l,int k,int n);
int swap(int *a,int *b);

int calculate_median(int arr[],int size)
{
    int temp;
    int i, j;
    for(i=0; i<size-1; i++) {
        for(j=i+1; j<size; j++) {
            if(arr[j] < arr[i]) {

                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }

    if(size%2==0) {

        return((arr[size/2] + arr[size/2 - 1]) / 2.0);
    } else {

        return arr[size/2];
    }
}

int medianOfmedians(int array1[],int f,int l,int k,int n)
{
    if(k>=0 && k<n)
{
int i,median[(n+4)/5];
int medians = 0 ;
int temporary[7];
int m=0;
int piv,ans;
for(i=0;i<=n;i+=5)
{
    if(i+5>n)
    {
        m = 0;
        temporary[m]=array1[i];
        temporary[m+1]=array1[i+1];
        median[medians]=calculate_median(temporary,n%5);
        medians+=1;
        temporary[m]=0;
        temporary[m+1]=0;
    }
    temporary[m]=array1[i];
    temporary[m+1]=array1[i+1];
    temporary[m+2]=array1[i+2];
    temporary[m+3]=array1[i+3];
    temporary[m+4]=array1[i+5];
    median[medians]=calculate_median(temporary,5);
    m = 0;
    medians+=1;
    temporary[m]=0;
    temporary[m+1]=0;
    temporary[m+2]=0;
    temporary[m+3]=0;
    temporary[m+4]=0;

}
int l = sizeof(median)/sizeof(int);
if(l==1)
{
    printf("GOT the pivot");
    piv = median[0];
}
else
{
piv=medianOfmedians(median,0,l-1,n/10,n);
}
ans=partition(array1,f,l,piv);
if(ans == k)
{
    return ans;
}
if(ans < k)
{
    medianOfmedians(array1,f,ans-1,k,n);
}
if(ans > k) 
{
    medianOfmedians(array1,array1[ans+1],l,k,n);
}
}
    return 0;
}

int swap(int *a,int *b)
{

    int temp=*a;
    *a=*b;
    *b=temp;
    return 0;
}

int partition(int a[],int f,int l,int x)
{

    int i;
    for(i=f;i<=l;i++)
    {

      if(a[i]==x)
      {
          break;
      }
    }
    swap(&a[i],&a[l]);
    i=f;
    for(int j=f;j<=l-1;j++)
    {
        if(a[j]<=a[l])
        {
            swap(&a[i],&a[j]);
            i++;
        }

    }
    swap(&a[i+1],&a[l]);
    return i+1;
}

int main(int argc, char *argv[])
{

    int k=3,small;
    int array[]={1,4,7,3,15,8,14};
    int n = sizeof(array)/sizeof(array[0]);
    small=medianOfmedians(array,array[0],array[n-1],k,n); 
    printf("The ith smallest number is : %d", small);
    return 0;
}

Приведенная выше программа используется для вычисления k-го наименьшего элемента с использованием процедуры медианы медиан.Поскольку нарезка массивов в C ограничена, я попытался создать подмассивы (n / 5 групповых массивов) напрямую.Однако основная проблема заключается в следующем: всякий раз, когда я ссылаюсь на массив из функции main() на medianOfmedians(), значения, полученные в функции, отличаются.Почему?

...