[Wiki] Binary Insert Sort in C

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

binary_insert_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(n^2)
  • xấu nhất: O(n^2)
  • tốt nhất: O(n)
  • 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);

inline void _sort_swap(type a,type b,int size){
    if(size>16){
        type t=malloc(size);
        assert(t!=0);
        memcpy(t,a,size);
        memcpy(a,b,size);
        memcpy(b,t,size);
        free(t);
    }else{
        char tmp[size];
        memcpy(tmp,a,size);
        memcpy(a,b,size);
        memcpy(b,tmp,size);
    }
}

#define A(i) ((a)+(i)*(size))

inline int binary_insert_sort_find(const type x,type a,const int n,
        int size,_sort_cmp_fn_t cmp){
    int l,r,c;
    type cx;
    l=0;
    r=n-1;
    c=r>>1;
    if(cmp(x,A(0))<0){
        return 0;
    }else if(cmp(x,A(r))>0){
        return r;
    }
    cx=A(c);
    while(1){
        const int val=cmp(x,cx);
        if(val<0){
            if(c-l<=1) return c;
            r=c;
        }else{
            if(r-c<=1) return c+1;
            l=c;
        }
        c=l+((r-l)>>1);
        cx=A(c);
    }
}

inline void binary_insert_sort_start(type a,const int start,const int n,
        _sort_cmp_fn_t cmp,int size){
    register int i,j,location;
    type x=malloc(size);
    assert(x!=0);
    for(i=start;i<n;++i){
        if(cmp(A(i-1),A(i))<=0) continue;
        memcpy(x,A(i),size);
        location=binary_insert_sort_find(x,a,i,size,cmp);
        for(j=i-1;j>=location;--j){
            memcpy(A(j+1),A(j),size);
        }
        memcpy(A(location),x,size);
    }
    free(x);
}

inline void binary_insert_sort(type a,const int n, int size,_sort_cmp_fn_t cmp){
    if(n<=1) return;
    binary_insert_sort_start(a,1,n,cmp,size);
}

#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
",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;
    binary_insert_sort(a,n,s,cmp);
    show(a,n);
    return 0;
}

#output
2 gio
2 honey_moon
3 ltd
3 nhim_xu