Heap Sort Using C language

Heap Sort

Heap sort is a one type of sorting algorithm.
Worst-case performance : O(n log n)
Best-case performance : Ώ(n), O(n log n)
Average-case performance : O(n log n)
For more information click here

Code

/*****Heap sort*****/
#include<stdio.h>
//Function declaration
void manage(int *, int);
void heapsort(int *, int, int);
//Main function start
int main(){
 int arr[20]; 
 int i,j,size,tmp,k;
 
 //Taking the number of element
  printf("Enter the number of elements to sort : ");
 scanf("%d",&size);
 
 //Taking the elements from user
 for(i=1; i<=size; i++) {
   printf("Enter %d element : ",i);
   scanf("%d",&arr[i]);
   manage(arr,i);
 }
 j=size;
 for(i=1; i<=j; i++) {
   //Swap
   tmp=arr[1];
   arr[1]=arr[size];
   arr[size]=tmp;
   size--;
   
   //Function call for heap sort
   heapsort(arr,1,size);
 }
 printf("\nAfter sorting the elements are: ");
 size=j;
 for(i=1; i<=size; i++)
     printf(" %d ",arr[i]);
 return 0;
}

//Function definition
void manage(int *arr, int i){
 int tmp; 
 tmp=arr[i];
 while((i>1)&&(arr[i/2]<tmp)) {
   arr[i]=arr[i/2];
   i=i/2;
 }
 arr[i]=tmp;
}

//Function definition
void heapsort(int *arr, int i, int size){
 int tmp,j;
 tmp=arr[i];
 j=i*2;
 while(j<=size) {
   if((j<size)&&(arr[j]<arr[j+1]))
      j++;
   if(arr[j]<arr[j/2]) 
      break;
   arr[j/2]=arr[j];
   j=j*2;
 }
 arr[j/2]=tmp;
}

Output

Enter the number of elements to sort : 7
Enter 1 element : 8
Enter 2 element : 4
Enter 3 element : 6
Enter 4 element : 9
Enter 5 element : 11
Enter 6 element : 2
Enter 7 element : 5

After sorting the elements are:  2  4  5  8  6  9  11

AVL Tree in C language

AVL Tree in C language

Use C programming language to make an AVL tree and display the tree in INORDER formate.

Code

/******AVL tree******/
#include <stdio.h>
#include <stdlib.h>

//Structure for tree
struct AVL 
{
 int data,height;
 struct AVL *left,*right;
};

//Function definition for getting maximum value
int max(int a,int b)
{
 if(a>=b)
  return a;
 else
  return b; 
}

//Function definition for getting the height of the tree
int height(struct AVL **root)
{
 if(*root==NULL)
  return 0;
 return (*root)->height; 
}

//Function definition for getting the balance factor of the tree
int balance(struct AVL **root)
{
 return(height(&((*root)->left))-height(&((*root)->right)));
}

//Function definition for rotate the tree right
void rightrotate(struct AVL **root)
{
 struct AVL *child,*temp;
 child=(*root)->left;
 temp=child->right;
 child->right=*root;
 (*root)->left=temp;
 (*root)->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
 child->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
 *root= child;
 
}

//Function definition for rotate the tree left
void leftrotate(struct AVL **root)
{
 struct AVL *child,*temp;
 child=(*root)->right;
 temp=child->left;
 child->left=*root;
 (*root)->right=temp;
 (*root)->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
 child->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
  *root=child;
}

//Function definition for creating
void create(struct AVL **root,int d)
{  int bal;
 if(*root==NULL)
 {
   *root=(struct AVL*)malloc(sizeof(struct AVL));
   (*root)->data=d;
   (*root)->height=1;
   (*root)->left=NULL;
   (*root)->right=NULL;
   return; 
 }
 else if(d > (*root)->data)
  create(&((*root)->right),d);
 else if(d < (*root)->data)
  create(&((*root)->left),d);
 else
   printf("item already exist");
 (*root)->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;  
 bal=balance(&(*root));
 if(bal< -1 && d < (*root)->right->data)
 {
  rightrotate(&((*root)->right));
  leftrotate(&(*root));
 }
 if(bal > 1 && d < (*root)->left->data)
  rightrotate(&(*root)); 
 if(bal < -1 && d < (*root)->right->data)
 {
  leftrotate(&(*root));
 }
 if(bal > 1 && d > (*root)->left->data)
 {
  leftrotate(&((*root)->left));
  rightrotate(&(*root));
 }
    
}

//Function definition for inorder traversal
void inorder(struct AVL **root)
{
 if(*root)
 {
  inorder(&((*root)->left));
  printf("%d\t",(*root)->data);
  inorder(&((*root)->right));
 }
}
int main()
{
 struct AVL *root=NULL;
 int ch,d;
 do
 {   
  printf("\n1.create or insert element to AVL tree");
  printf("\n2.inorder display element to tree");
  printf("\n3.exit");
  printf("\nenter ur choice");
  scanf("%d",&ch);
  switch (ch)
  {
   case 1:
    printf("\nenter element to new node");
    scanf("%d",&d);
    create(&root,d);
    break;
   case 2:
    inorder(&root);
    getch();
    break;
   case 3:
    exit(0);
   default:
    printf("invalid choice");   
  }
 }while(1);
 return (0); 
}

Output

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node10

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node5

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node15

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node3

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node2

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node6

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice2
2       3       5       6       10      15

Hashing Using C language

Hashing Using C language

Create a Hash Table in C language and search table elements.

Code

/*****Hashing technique and collision resolution******/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

//Creating structure
struct Hash{
 int info;
 struct Hash *next;
};

//Function declaration
void search(struct Hash *key,int n);
void display(struct Hash *key,int n);
void insert(struct Hash **key,int n);

int main(){
 int n,i,choice;
 struct Hash *key;
 printf("Enter no of key you want to create:\t");
 scanf("%d",&n);
 key=(struct Hash *)calloc(n,sizeof(struct Hash));
 for(i=0;i<n;i++){
 (key+i)->info=i;
 (key+i)->next=NULL;
 }
 display(key,n);
 while(1){
  printf("\nOPTIONS\n");
  printf("1.Insert\n");
  printf("2.Search\n");
  printf("3.Exit\n");
  printf("Enter choice:\t");
  scanf("%d",&choice);
  switch(choice){
    case 1: insert(&key,n);
      display(key,n);
      break;

    case 2: display(key,n);
      search(key,n);
      break;

    case 3: exit(0);
   default: printf("Enter correct option!!!");
  }
 }
}

//Function definition for insert
void insert(struct Hash **key,int n){
  struct Hash *temp;
  int formulae,element;
   temp=(struct Hash *)calloc(1,sizeof(struct Hash));
   printf("Enter the element:\t");
   scanf("%d",&element);
   temp->info=element;
   temp->next=NULL;
   formulae = element % n;
   if ((*key+formulae)->next==NULL)
   (*key+formulae)->next=temp;
   else{
   temp->next=(*key+formulae)->next;
   (*key+formulae)->next=temp;
   }
}
//Function definition for Display
void display(struct Hash *key,int n){
  int i;
  struct Hash *temp;
  printf("Key\tElements");
 for(i=0;i<n;i++){
  temp=(key+i);
  printf("\n");
  while(temp!=NULL){
   printf("%d\t",(temp)->info);
   temp=temp->next;
  }
 }
}
//Function defination for search
void search(struct Hash *key,int n){
 int search_element,key_index,column=1,i=0;
  struct Hash *temp;
  printf("\nEnter the element to search:\t");
  scanf("%d",&search_element);
  key_index=search_element%n;
  temp=(key+key_index)->next;
 while(temp!=NULL){
  if (temp->info==search_element){
   printf("[%d] is present at [%d] row and [%d] column.",search_element,key_index,column);
   i=1;
  }
  temp=temp->next;
  column=column+1;
 }
 if(i==0)
  printf("[%d] is not present in Hash table.",search_element);
}

Output

Enter no of key you want to create:     5
Key     Elements
0
1
2
3
4
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      10
Key     Elements
0       10
1
2
3
4
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      54
Key     Elements
0       10
1
2
3
4       54
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      69
Key     Elements
0       10
1
2
3
4       69      54
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      87
Key     Elements
0       10
1
2       87
3
4       69      54
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      21
Key     Elements
0       10
1       21
2       87
3
4       69      54
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   2
Key     Elements
0       10
1       21
2       87
3
4       69      54
Enter the element to search:    54
[54] is present at [4] row and [2] column.
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   2
Key     Elements
0       10
1       21
2       87
3
4       69      54
Enter the element to search:    21
[21] is present at [1] row and [1] column.
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   2
Key     Elements
0       10
1       21
2       87
3
4       69      54
Enter the element to search:    58
[58] is not present in Hash table.
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   3