HEAP SORT

#include<stdio.h>

#define N 1000

void build_heap(int *a,int size,int key);

int heap_delete(int *a,int size,int key);

int main()

{

int a[N],b[N],key,choice;

int i,size=0;

int result;

printf("Enter numbers followed by -9999 to stop \n");

for(i=0;;i++)

{

scanf("%d",&key);

if(key==-9999)

{

break;

}

build_heap(a,i,key);

}

size=i;

printf("heaped size %d \n",size);

for(i=1;i<=size;i++)

{

printf("%d ",a[i]);

}

while(1)

{

printf("\nEnter\n1 - ADD \n2 - Delete \n3 - Sort \n0 - Exit\n");

scanf("%d",&choice);

if(choice == 3)

{

printf("sorted \n");

for(i=1;i<=size;i++)

{

b[i]=a[i];

}

for(i=0;i<size;i++)

{

printf("%d ",b[1]);

heap_delete(b,size-i,b[1]);

}

}

else if(choice == 2)

{

printf("Enter the number to be deleted \n");

scanf("%d",&key);

result = heap_delete(a,size,key);

if(result)

size--;

printf("New heap \n");

for(i=1;i<=size;i++)

{

printf("%d ",a[i]);

}

}

else if (choice == 1)

{

printf("Enter the number to be Added \n");

scanf("%d",&key);

build_heap(a,size,key);

size++;

printf("New heap \n");

for(i=1;i<=size;i++)

{

printf("%d ",a[i]);

}

}

else

{

break;

}

}

return 0;

}

void build_heap(int *a,int size,int key)

{

int i,j,temp;

/*Add element to the end*/

a[size+1]=key;

j=size+1;

/*Adjust the heap by moving the new element to right position */

while(j>1 && a[j] > a[j/2])

{

temp = a[j];

a[j] = a[j/2];

a[j/2] = temp;

j=j/2;

}

return;

}

int heap_delete(int *a,int size,int key)

{

int i,j,temp;

/*Return if heap size is zero */

if(size == 0)

return 0;

for(i=1;i<=size;i++)

{

if(key==a[i])

{

/* Replace the deleted element with the

last element in the Heap */

a[i]=a[size];

/*store the element at the end*/

a[size] = key;

break;

}

}

/*Return if Key is not found*/

if(i == size+1)

{

printf(" Key not available \n");

return 0;

}

j=i*2;

/*Adjust the heap*/

while(j < size)

{

/* move to the greater leaf */

if ((j < size-1) && (a[j]<a[j+1]))

j++;

if(a[j/2] < a[j])

{

temp = a[j/2];

a[j/2] = a[j];

a[j] = temp;

j= j*2;

}

else

{

break;

}

}

return 1;

}

MERGE SORT

/*
 * Merge Sort -
 * This is recursive function
 * O(n log(n))
  */


void merge_sort(int *list,int start,int end)
{
   /* recursing should be stoppped if start > end */
    if(start<end)
    {
        /* swap for merging two elements*/
        if(end-start == 1)
        {
            if(list[start]>list[end])
            {
                list[end]   = list[end] ^ list[start];
                list[start]   = list[end] ^ list[start];
                list[end] = list[end] ^ list[start];
            }
        }
        else
        {

            merge_sort(list,start, (start+end)/2);
            merge_sort(list,(start+end)/2+1,end);
            merge(list,start,(start+end)/2,end);
        }
    }
}

/*
 * Function to merge two arrays
 * To avoid memory wastage malloc used. Otherwise array of max size can be used
 */
void merge(int *list,int start,int middle,int end)
{
    int i,j,k,l;
    int *temp; /* if not dynamic max size should be used*/

    temp = (int *)malloc(sizeof(int)*(end-start+1));
    i=start;
    j=middle+1;
    k=0;
    while(1)
    {
       /* store the small element into temp array*/
        if(list[i]<list[j])
        {
            temp[k++]=list[i++];
        }
         else
        {
            temp[k++] = list[j++];
        }
      /* Check if any of the arrays are finished. If so append the other array*/
        if(i>middle)
        {
            for(;j<=end;j++)
                temp[k++]=list[j];
            break;
        }
        else if(j>end)
        {
            for(;i<=middle;i++)
                temp[k++]=list[i];
            break;
        }
    }
   /*  Fill the original array with merge sorted*/
    k=0;
    for(i=start;i<=end;i++)
    {
        list[i]=temp[k++];
    }

}

REVERSE LINKS IN LINKED LIST

/ * 

  *Reverse a linked list

  * This program reverse the links in a linked list. but not the data.

  */

void reverse_link(NODE **root)

{

    NODE *p,*q,*r=NULL;

    if(*root == NULL)

        return;

    p=*root;

    if(p->next != NULL)

    {

        q=p->next;

        p->next = NULL;

        while(q!=NULL)

        {

            r=q->next;  /* First store the next link address */

            q->next=p; /*  Reverse the link */

            p=q;           /* Move forward */

            q=r;

        }

        *root = p;  /* root is at last node */

    }

    return;

}

INSERTION SORT

/* Insertion Sort is simplest in-place sort algorithm to sort an array*/

 /* The code for the algorithm is as given below */


void insertion_sort(int *list, int size)
{
    int i,j;

    for(i=1;i<size;i++)
    {
        for(j=i;j>0;j--)
        {
            if(list[j]>list[j-1])
            {   /* SWAP */
                list[j]   = list[j]^list[j-1];
                list[j-1] = list[j]^list[j-1];
                list[j]   = list[j]^list[j-1];
            }
            else
            {
                break;
            }
        }
    }
return;
}