[Wiki] Merge Sort in C

[Gio (Gió)]

####Hôm nay rảnh rỗi, viết hàm merge_sort chơi

• Cách Dùng: Tương tự hàm qsort trong thư viện stdlib.h

merge_sort(mảng, số lượng phần tử, kích thước 1 phần tử, hàm so sánh);

• độ phức tạp:

• trung bình: O(nlogn)
• xấu nhất: O(nlogn)
• bộ nhớ: O(n)

• source code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>

#define __sort
#define type void*
typedef int (*_sort_cmp_fn_t)(const type,const type);
#define A(i) ((a)+(i)*(size))
inline void merge_sort(type a,const int n,int size,_sort_cmp_fn_t cmp){
    if(n<2){
        return;
    }
    type newa=malloc(n*size);
    assert(newa!=NULL);
    int mid=n/2;
    merge_sort(a,mid,size,cmp);
    merge_sort(A(mid),n-mid,size,cmp);
    register int i=0,j=mid,out=0;
    while(out<n){
        if(i<mid){
            if(j<n){
                if(cmp(A(i),A(j))<=0){
                    memcpy(newa+out*size,A(i),size);
                    i++;
                }else{
                    memcpy(newa+out*size,A(j),size);
                    j++;
                }
            }else{
                memcpy(newa+out*size,A(i),size);
                i++;
            }
        }else{
            memcpy(newa+out*size,A(j),size);
            j++;
        }
        out++;
    }
    memcpy(a,newa,size*n);
    free(newa);
}
#undef A
#undef type
#undef __sort

typedef struct{
    char name[20];
    int level;
} user;
void show(user *a,int n){
    int i;
    for(i=0;i<n;++i){
        printf("%d %s\n",a[i].level,a[i].name);
    }
}
int cmp(const void *a,const void *b){
    const user *x=a,*y=b;
    if(x->level!=y->level) return x->level-y->level;
    return strcmp(x->name,y->name);
}
int main(){
    user a[]={
        {"gio",2},
        {"ltd",3},
        {"honey_moon",2},
        {"nhim_xu",3}
    };
    int s=sizeof(user);
    int n=sizeof(a)/s;
    int i;
    merge_sort(a,n,s,cmp);
    show(a,n);
    return 0;
}

output
2 gio
2 honey_moon
3 ltd
3 nhim_xu

[DungJun (Nguyễn Đình Dũng)]

Mời ae cùng ngâm cứu

[Long_Cao]

video của bạn rất thú vị