heapsort.c

/*Work easy...!!...Play hard*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node
{
        int data;
        struct node *next;
};
void addnode(struct node **hd,struct node **st)
{
        struct node *new,*temp;
        new = (struct node*)malloc(sizeof(struct node));
        new->data = (*st)->data;
        new->next = NULL;
        if(*hd == NULL)
        {
                *hd = new;
        }
        else
        {
                temp = *hd;
                while(temp->next != NULL)
                {
                        temp = temp->next;
                }
                temp->next = new;
        }
}
void display(struct node **hd)
{
        struct node *temp=*hd;
        while(temp != NULL)
        {
                printf("%d ",temp->data);
                temp = temp->next;
        }
        puts("");
}

void swap(int *a,int *b)
{
        int t;
        t = *a;
        *a = *b;
        *b = t;
}
void minheap(struct node **hd,int count)
{
        int flag = 1,m,i,j,k;
        m = (count-1)/2;
        while(flag)
        {
                flag = 0;
                for(i=m;i>=0;i--)
                {
                        struct node *temp,*templ,*tempr;
                        temp = templ = tempr = *hd;
                        for(j=0;j<i;j++)
                                temp = temp->next;
                        for(k=0;k<(2*j)+1;k++)
                        {
                                if(templ == NULL)
                                        break;
                                templ = templ->next;
                        }
                        for(k=0;k<(2*j)+2;k++)
                        {
                                if(tempr == NULL)
                                        break;
                                tempr = tempr->next;
                        }
                        if(templ != NULL && templ->data < temp->data)
                        {
                                swap(&(templ->data),&(temp->data));
                                flag = 1;
                        }
                        if(tempr != NULL && tempr->data < temp->data)
                        {
                                swap(&(tempr->data),&(temp->data));
                                flag = 1;
                        }
                }
        }
}
int delete(struct node **hd)
{
        int x = (*hd)->data;
        if(*hd == NULL)
                return;
        else
                *hd = (*hd)->next;
        return x;
}
void heapsort(struct node **hd,int count)
{
        int i,x;
        minheap(hd,count);
        for(i=0;i<count;i++)
        {
                x = delete(hd);
                printf("%d ",x);
                minheap(hd,count-(i+1));
        }
        puts("");
}
int main(int argc,char *argv[])
{
        if(argc != 2){puts("Invalid no. of arguments");exit(1);}
        FILE *fp;
        if((fp=fopen(argv[1],"r")) == NULL){puts("Can't open");exit(1);}

        int count=0;
        struct node *st,*hd=NULL;
        st =(struct node*)malloc(sizeof(struct node));

        while((fscanf(fp,"%d",&(st->data))) != EOF)
        {
                addnode(&hd,&st);
                count++;
        }
        //display(&hd);
        heapsort(&hd,count);
}