Sort Algorithm

sort_algorithm.c

/*
quick sort  v1
http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
*/
#include<stdio.h>
void qsort(int a[],int left,int right);
int findp(int v[],int left,int right);//find pivot position
void swap(int *,int *);
int main(){
    int a[]={5,4,3,1,4,5,6,8,9,0};
    qsort(a,0,9);
    int i;
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}
int findp(int v[],int left,int right){
    int p=v[left];//initialize pivot=v[left]
    int l=left+1,r=right;
    while(l<r){
        while(v[l]<=p && l<r)
            l++;
        while(v[r]>=p && r>l)
            r--;
        swap(v+l,v+r);
    }
    //what if v==l
    if(v[l]>=p){
        swap(v+left,v+l-1);
        return l-1;
    }
    else{
        swap(v+left,v+l);
        return l;
    }

}
void swap(int *a,int *b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
void qsort(int v[],int left,int right){
    if(left>=right)
        return;
    int pivot=findp(v,left,right);
    int i;
    for(i=left;i<=right;i++)
        printf("%d  ",v[i]);
    printf("\n");
    qsort(v,left,pivot-1);
    qsort(v,pivot+1,right);

}
/*output
0  4  3  1  4  5  5  8  9  6  
0  4  3  1  4  5  
4  3  1  4  5  
1  3  4  
1  3  
6  8  9  
0 1 3 4 4 5 5 6 8 9 
*/
/*....quick sort v2...*/
#include <stdio.h>
#include <string.h>
#define NELEMS(s) (int)(sizeof(s)/sizeof(s[0]))
void Qsort(void *v[],int left,int right,int (*cmp)(void *,void *));
void Swap(void **,void **);
int main(){
    char *s[]={"q","w","e","r","t","y","u","i"};
    int n=NELEMS(s);
    Qsort((void **)s,0,n-1,(int(*)(void *,void *))(strcmp));
    int i=0;
    for(;i<n;i++)
        printf("%s ",s[i]);
    printf("\n");
    return 0;
}
void Qsort(void *v[],int left,int right,int (*cmp)(void *,void *)){
    if(left>=right)
        return ;
    //find pivot
    void *p=v[left];
    int pivot=left;//pivot position
    int iter;
    for(iter=left+1;iter<=right;iter++)
        if((*cmp)(v[iter],p)<0)
            Swap(v+iter,v+(++pivot));
    Swap(v+left,v+pivot);// partion ok
    Qsort(v,left,pivot-1,cmp);
    Qsort(v,pivot+1,right,cmp);
}
void Swap(void **s,void **t){
    void *temp;
    temp=*s;
    *s=*t;
    *t=temp;
}


/*
shell sort
http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
*/
#include <stdio.h>
void InsertSort(int a[],int start,int step,const int len);//rewirte from Insertion Sort
int main(){
    int a[]={9,8,7,6,5,4,3,2,1,0};
    int len=sizeof(a)/sizeof(int);
    int step=len,i;
    while((step/=2)>0){
        for(i=0;i<step;i++)//reference wiki
            InsertSort(a,i,step,len);
    }
    for(i=0;i<len;i++)
        printf("%d%c",a[i],(i==len-1)?'\n':' ');
    return 0;
}
void InsertSort(int a[],int start,int step,const int len){
    int k,i,key;//k for key position,i for insert position
    for(k=start;k<len;k+=step){
        key=a[k];
        i=k-step;
        while(i>=start && key<=a[i]){
            a[i+step]=a[i];
            i-=step;
        }
        a[i+step]=key;
    }
}
/*
string sort
reference:quick sort,dynamic string
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INITIALSIZE 3
#define INCREMENT 10
int GetString(char *s,char **sp,unsigned int InitialSize);
void WriteString(char **sp,unsigned int l);
void Swap(char **s,char **t);
int Findp(char **sp,int left,int right);
void QSort(char **sp,int left,int right);
int main(){
    unsigned int CurrentLine=INITIALSIZE;
    char **Lines=malloc(CurrentLine*sizeof(char *));//类比
    //char *Lines[20];
    int L=0;
    while(GetString(Lines[L],Lines+L,INITIALSIZE)>0){
        L++;
        if(L==CurrentLine){
            CurrentLine+=INCREMENT;
            Lines=(char **)realloc(Lines,CurrentLine*sizeof(char *));
        }
    }
    QSort(Lines,0,L-1);
    WriteString(Lines,L);
}
int GetString(char *s,char **sp,unsigned int InitialSize){
    s=malloc(InitialSize);
    int c;
    unsigned int current_size=InitialSize;
    unsigned int len=0;
    while((c=getchar())!=EOF && c!='\n'){//END: EOF or "\n\n" 
        s[len++]=c;
        if(len==current_size){
            current_size+=INCREMENT;
            s=realloc(s,current_size);
        }
    }
    s[len]='\0';
    *sp=s;
    return len;

}
void WriteString(char **sp,unsigned int l){
    int i;
    for(i=0;i<l;i++)
        printf("%s\n",sp[i]);
}
void QSort(char **sp,int left,int right){
    if(left>=right)
        return;
    int pivot=Findp(sp,left,right);
    QSort(sp,left,pivot-1);
    QSort(sp,pivot+1,right);
}
int Findp(char **sp,int left,int right){//类比 元素a[i]  地址a+i
    char *p=sp[left];
    int l=left+1,r=right;
    while(l<r){
        while(strcmp(sp[l],p)<=0 && l<r)
            l++;
        while(strcmp(sp[r],p)>=0 && r>l)
            r--;
        Swap(sp+l,sp+r);
    }
    if(strcmp(sp[l],p)>=0){
        Swap(sp+left,sp+l-1);
        return l-1;
    }
    else{
        Swap(sp+left,sp+l);
        return l;
    }
}
void Swap(char **s,char **t){
    char *temp;
    temp=*s;
    *s=*t;
    *t=temp;
}

/*binary tree sort*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define LIMIT 20
#define STRCONSTANT 0
#define COMMENT 1
#define WORD 2
#define PREPRO 3
#define BRACKET 4
#define NORMAL 5

/*char get and unget*/
#define STACKSIZE 10
int top=0;
int buffer[STACKSIZE];
int getch(void){
    return (top==0)?getchar():buffer[--top];
}
void ungetch(int c){
    if(top==STACKSIZE-1)
        printf("buffer full.\n");
    else
        buffer[top++]=c;
}

/*struct key node*/
typedef struct node{
    char *key;
    int count;
    struct node *left;
    struct node *right;
}Node;

/*deal word in inputstream*/
int GetWord(char *word, int lim);
int Classify(char c);
void HandleStr(char c);//skip string constants
void HandleCom(char c);//skip comments
void HandlePre(char c);//skip pre processor
void HandleBra(char c);//skip () and []
void HandleWord(char c, char *word,int lim);
int IsWord(char c);

/*add a word into key tree*/
Node *addtree(Node *,char*);
void treeprint(Node*);
char *Strdup(char *);//important

int main(){
    Node *root=NULL;
    char word[LIMIT];
    int class;
    while((class=GetWord(word,LIMIT))!=EOF){
        if(class==WORD){
            root=addtree(root,word);
        }
    }
    treeprint(root);
    return 0;
}
int GetWord(char *word,const int lim){
    int getch(void);//getchar from input
    void ungetch(int);//putchar back to buffer
    int c;
    //skip space
    while(isspace(c=getch()))
        ;
    switch(Classify(c)){
        case EOF:
            return EOF;
            break;
        case STRCONSTANT://skip string constants
            HandleStr(c);
            return STRCONSTANT;
            break;
        case COMMENT://skip comments
            HandleCom(c);
            return COMMENT;
            break;
        case WORD:
            HandleWord(c,word,lim);
            return WORD;
            break;
        case PREPRO:
            HandlePre(c);
            return PREPRO;
            break;
        case BRACKET:
            HandleBra(c);
            return BRACKET;
            break;
        default:
            return NORMAL;
    }
}
int Classify(char c){
    if(c==EOF)
        return EOF;
    else if(c=='"')
        return STRCONSTANT;
    else if(c=='/')
        return COMMENT;
    else if(c=='_' || isalpha(c))
        return WORD;
    else if(c=='#')
        return PREPRO;
    else if(c=='[' || c=='(')
        return BRACKET;
    else
        return NORMAL;
}
void HandleStr(char c){
    int ch;
    while((ch=getch())!='"')
        ;
}
void HandleCom(char c){
    int ch;
    if((ch=getch())=='*')
        while((ch=getch())!='/')
            ;
    else
        while((ch=getch())!='\n')
            ;
}
void HandlePre(char c){
    int ch;
    while((ch=getch())!='\n')
        ;
}
void HandleBra(char c){
    int ch;
    int bra=1;
    while((ch=getch())){
        if(ch=='('||ch=='[')
            bra++;
        else if(ch==')'||ch==']')
            bra--;
        if(bra==0)
            break;
    }
}
void HandleWord(char c, char *word,int lim){
    *word++=c;
    int ch;
    for(;--lim>0;word++)
        if(!IsWord(*word=getch())){
            ungetch(*word);
            break;
        }
    *word='\0';

}
int IsWord(char c){
    return (isalnum(c) || c=='_')?1:0;
}
Node *addtree(Node *r,char *w){
    int cmp;
    if(r==NULL){
        r=(Node *)malloc(sizeof(Node));
        r->key=Strdup(w);
        r->count=1;
        r->left=r->right=NULL;
    }
    else if((cmp=strcmp(r->key,w))==0)
        r->count++;
    else if(cmp<0)
        r->right=addtree(r->right,w);
    else
        r->left=addtree(r->left,w);
    return r;
}
void treeprint(Node *r){
    if(r!=NULL){
        treeprint(r->left);
        printf("%4d %s\n",r->count,r->key);
        treeprint(r->right);
    }
}
char *Strdup(char *s){
    char *p;
    p=(char *)malloc(strlen(s)+1);
    if(p!=NULL)
        strcpy(p,s);
    return p;
}

/*hash sort*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 20
#define HASHSIZE 101
/*hash table*/
typedef struct hlist{
    struct hlist *next;
    char *key;
    char *defn;
}Hlist;
Hlist *hashtab[HASHSIZE];

/*hash function f(key)=hashval */
unsigned hash(char *key){
    unsigned hashval=0;
    while(*key!='\0'){
        hashval=31*hashval+*key;
        key++;
    }
    hashval%=HASHSIZE;
    return hashval;
}

/*look up for a key*/
Hlist *Lookup(char *key){
    Hlist *hp;
    hp=hashtab[hash(key)];
    while(hp && strcmp(key,hp->key)!=0)
        hp=hp->next;
    return hp;
}

Hlist *Install(char *key,char *defn){
    Hlist *hp;
    hp=Lookup(key);
    if(hp==NULL){
        hp=(Hlist *)malloc(sizeof(Hlist));
        if(hp==NULL || (hp->key=strdup(key))==NULL || (hp->defn=strdup(defn))==NULL)
            return NULL;
        hp->next=hashtab[hash(key)];//insert new at the head
        hashtab[hash(key)]=hp;
    }
    else
        free(hp->defn);
    if((hp->defn=strdup(defn))==NULL)
        return NULL;
    printf("success\n");
    return hp;
}
int main(){
    char key[SIZE],defn[SIZE],query[SIZE];
    printf("input your query key: ");
    scanf("%s",query);
    while(scanf("%s %s",key,defn)!=EOF){
        Install(key,defn);
    }
    Hlist *hp;
    if((hp=Lookup(query)))
        printf("key:%s  defn:%s\n",hp->key,hp->defn);
    else
        printf("%s not in hashtable\n",query);
    return 0;
}

Strdup know about malloc