[Wiki] Heap Sort in C

[Gio (Gió)]

Continuing the discussion from [Wiki] Merge Sort in C:

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

heap_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);

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 void heap_sift_down(type a,int size,
        _sort_cmp_fn_t cmp,int start,int end){
    register int child,root=start;
    while((root<<1)<=end){
        child=root<<1;
        if(child<end && cmp(A(child),A(child+1))<0){
            child++;
        }
        if(cmp(A(root),A(child))<0){
            _sort_swap(A(root),A(child),size);
            root=child;
        }else return;
    }
}
inline void heapify(type a,int size,_sort_cmp_fn_t cmp,int n){
    register int start=n>>1;
    while(start>=0){
        heap_sift_down(a,size,cmp,start,n-1);
        start--;
    }
}
inline void heap_sort(type a, int n,int size,_sort_cmp_fn_t cmp){
    register int end;
    if(n<2) return;
    end=n-1;
    heapify(a,size,cmp,n);
    while(end>0){
        _sort_swap(A(end),a,size);
        heap_sift_down(a,size,cmp,0,end-1);
        end--;
    }
}
#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;
    heap_sort(a,n,s,cmp);
    show(a,n);
    return 0;
}

#output:
2 gio
2 honey_moon
3 ltd
3 nhim_xu