병합 정렬을 사용하여 배열 정렬

Question

코드가 올바른 것으로 보이지만 병합 정렬을 위해 구현되었습니다. 정렬 된 배열은 정렬 된 배열을 제공하지 않고 오히려 동일한 배열을 반환하므로 내 병합을 의미합니다. 여기

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

마지막 left

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

Answer 1

작동하지의 기능은 right해야한다.

어쨌든, 어디에서 free 너는 malloc -ed ...?

Answer 2

malloc 모든 재귀 호출에서 각 하위 배열에 대해 새 버퍼를 작성하는 것은 매우 나쁜 생각입니다. 기억하십시오. malloc은 매우 비싼 행동이며, free은 심지어 malloc 이상의 비용이 듭니다.

재귀 적 분할로 인한 하위 배열은 겹치지 않습니다 (병합 된 두 부분의 병합 결과 제외). 따라서 병합 결과가 및 인 경우 한 번에 개를 하나씩 버퍼만큼 필요로하지 않으므로 병합은 다른 병합 (하위 범위 인 경우 제외)을 방해하지 않습니다. 따라서 단지 을 전체 입력 배열의 단일 복사본을 만들고 재귀 병합의 소스 위치와 도착지로 다르게 두 배열을 사용하여 충분히 :

void merge(int dst[], int src[], int idx1, int idx2, int end2) 
{ 
    int idx = idx1; 
    int end1 = idx2; 

    while(idx1 < end1 && idx2 < end2) 
     dst[idx++] = src[idx1] <= src[idx2] ? src[idx1++] : src[idx2++]; 
    while(idx1 < end1) 
     dst[idx++] = src[idx1++]; 
    while(idx2 < end2) 
     dst[idx++] = src[idx2++]; 
} 

void mrgsrt(int dst[], int src[], int begin, int len) 
{ 
    if(len == 1) 
     dst[begin] = src[begin]; 
    if(len > 1) { 
     int mid = len/2; 
     mrgsrt(src, dst, begin, mid); 
     mrgsrt(src, dst, begin+mid, len-mid); 
     merge(dst, src, begin, begin+mid, begin+len); 
    } 
} 

void sort(int a[], int len) 
{ 
    int *tmp; 
    if((tmp = malloc(len*sizeof(*a))) != NULL) { 
    memcpy(tmp, a, len*sizeof(*a)); 
    mrgsrt(a, tmp, 0, len); 
    free(tmp); 
    } 
}