使用合并排序对数组进行排序 [英] Sorting of an array using merge sort

问题描述

我已经在c中实现了合并排序，尽管代码似乎是正确的，但是代码并没有给我排序后的数组，而是返回给它的相同数组，这意味着我的合并功能无法正常工作

I have implemented for merge sort in c , although the code seems to be correct the code does not give me the sorted array rather returns the same array that is given to it, that means my merge function in not working

#include<stdio.h>
#include<stdlib.h>

void re_sort(int arr[],int size);
void merge(int left[],int right[],int arr[],int rightlen,int leftlen);

int main(void)
{ 
  int a[10];
  int n;

  printf("enter the number\n");

  scanf("%d",&n);

    printf("enter the elements\n");
    for(int i=0;i<n;i++)

      {  
         scanf("%d",&a[i]);
      }

    re_sort(a,n);          //merge sort using recursion  

    printf("the sorted list is:\n");
    for(int i=0;i<n;i++)

      {  printf("%d\t",a[i]);

      }


    return 0;
}

void re_sort(int arr[],int size)

{  int mid,*left,*right;
   int k=0;
  if(size<2)            
    return; 

  else 
  mid=size/2;
  left=(int*)(malloc(mid*(sizeof(int))));          // two sub arrays left and right 
  right=(int*)(malloc((size-mid)*(sizeof(int))));

  for(int i=0;i<mid;i++)
  { 
    left[i]=arr[k++];
  }

  for(int j=0;j<(size-mid);j++)
  { 
    right[j]=arr[k++];
  }

  re_sort(left,mid);                 //recursion until size becomes less than 2
  re_sort(right,size-mid);
  merge(left,right,arr,size-mid,mid); //both the elements in left and right are merged



}
void merge(int left[],int right[],int arr1[],int rightlen,int leftlen)

{   int arr[100];
    int k=0,i=0,j=0;
    while(i<leftlen && j<rightlen)
    { 
      if(left[i]<= right[j])

      arr[k++]=left[i++];

      else 

      arr[k++]=right[j++];

    }

    while(i<leftlen)
    {
        arr[k++]=left[i++];
    } 
    while(j<rightlen)

    { 
       arr[k++]=right[j++];
    }

    for(int l=0;l<(rightlen+leftlen);l++)
    { 
      arr1[l]=arr[l];
    }
    free(left);
    free(right);
}

推荐答案

此处

  if(left[i]<= right[j])
      arr[k++]=left[i++];
  else 
      arr[k++]=left[j++];

最后一个left应该是right.

无论如何，您将malloc -ed ...的内存保存在哪里?

Anyway, where do you free the memory you malloc-ed...?

这篇关于使用合并排序对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！