Bubble Sort in C language

Bubble Sort

This is a one kind of sorting technique. The complexity of this sorting technique is,
Worst-case performance : O(n^2)
Best-case performance : O(n)
Average-case performance : O(n^2)
For more details click here

Code

/******Bubble Sort*****/

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//Function defination
int* bubble_sort(int *arr,int *n){
 int i,j,flag,temp;
 for(i=*n-1;i>=0;i--) {
  flag=0;
  for(j=0;j<i;j++)
   if(arr[j]>arr[j+1]){
    //Swapping
    temp=arr[j];
    arr[j]=arr[j+1];
    arr[j+1]=temp;
    flag=1;
   }
  if(flag==0)
   break;
 }
 return arr;
}

//Starting the main function
int main(){
 int *arr,n,i;
 while(1) {
  //Taking the number of element
  printf("\nEnter the number of element you want to store:");
  scanf("%d",&n);
  if(n<=0){
   printf("\nAn array size must be a positive integer.");
   continue;
  }
  else
   break;
 }
 //Creating array dynamically
 arr=(int*)malloc(n*sizeof(int));
 if(!arr){
  printf("\nNot enough memory.");
  exit(0);
 }
 printf("\nEnter the element(s) in the array:");
 for(i=0;i<n;i++){
  printf("\nElement[%d]:",i+1);
  scanf("%d",&arr[i]);
 }
 printf("\nThe element(s) before sorting:");
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 printf("\nThe element(s) after sorting:");
 arr=bubble_sort(arr,&n);
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 return 0;
}

Output

Enter the number of element you want to store:7

Enter the element(s) in the array:
Element[1]:6

Element[2]:1

Element[3]:8

Element[4]:4

Element[5]:5

Element[6]:2

Element[7]:3

The element(s) before sorting: 6 1 8 4 5 2 3
The element(s) after sorting: 1 2 3 4 5 6 8

Merge Sort in C language

Merge Sort

This is a one kind of sorting technique. The complexity of this sorting technique is,
Worst-case performance : O(n log n)
Best-case performance : O(n log n)
Average-case performance : O(n log n)
For more details click here

Code

/******Merge Sort*****/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//Function declaration
int* merge(int*,int,int,int);
//Function definition for merge sort
int* merge_sort(int *arr,int left,int right){
 int mid;
 if(right>left){
  mid=(left+right)/2;
  merge_sort(arr, left, mid);
  merge_sort(arr,mid+1,right);
  merge(arr,left,mid+1,right);
 }
 return arr;
}
//Function definition for merge two array
int* merge(int *arr,int left,int mid,int right){
 int *temp,i,x,no_of_element;
 no_of_element=right-left+1;
 x=left;
 temp=(int*)malloc(no_of_element*sizeof(int)); 
 while((left<=mid-1)&&(mid<=right)) {
  if(arr[left]<=arr[mid])  {
   temp[x++]=arr[left];
   left++;
  }
  else  {
   temp[x++]=arr[mid];
   mid++;
  }
 }
 while(left<=mid-1)
  temp[x++]=arr[left++];
 while(mid<=right)
  temp[x++]=arr[mid++];
 for(i=0;i<no_of_element;i++) {
  arr[right]=temp[right];
  right--;
 }
 return arr;
}
//Main function start
int main()
{
 int *arr,n,i;
 while(1){
  //taking the number of element
  printf("\nEnter the number of element you want to store:");
  scanf("%d",&n);
  if(n<=0){
   printf("\nAn array size must be a positive integer.");
   continue;
  }
  else
   break;
 }
 //Creating array dynamically
 arr=(int*)malloc(n*sizeof(int));
 if(!arr){
  printf("\nNot enough memory.");
  exit(0);
 }
 //Taking the element from user
 printf("\nEnter the element(s) in the array:");
 for(i=0;i<n;i++){
  printf("\nElement[%d]:",i+1);
  scanf("%d",&arr[i]);
 }
 //Print the element before sorting
 printf("\nThe element(s) before sorting:");
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 printf("\nThe element(s) after sorting:");
 //Call the function
 arr=merge_sort(arr,0,n-1);
 //Print the sorted array
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 return 0;
}

Output

Enter the number of element you want to store:5

Enter the element(s) in the array:
Element[1]:1

Element[2]:8

Element[3]:3

Element[4]:2

Element[5]:5

The element(s) before sorting: 1 8 3 2 5
The element(s) after sorting: 1 2 3 5 8

Quick Sort in C language

Quick Sort

This is a one kind of sorting technique. The complexity of this sorting technique is,
Worst-case performance : O(n^2)
Best-case performance : O(n log n)
Average-case performance : O(n log n)
For more details click here

Code

/******Quick Sort*****/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//Function definition
int* quick_sort(int *arr,int low,int high){
 int pivot,i,temp,j;
 if(low<high) {
  pivot=arr[low];
  i=low;
  j=high;
 }
 else
  return arr;
 while(i<j){
  while((arr[i]<=pivot)&&(i<high))
   i++;
  while((arr[j]>=pivot)&&(j>low))
   j--;
  if(i<j){
   temp=arr[i];
   arr[i]=arr[j];
   arr[j]=temp;
  }
 }
 temp=arr[low];
 arr[low]=arr[j];
 arr[j]=temp;
 quick_sort(arr,low,j-1);
 quick_sort(arr,j+1,high); 
}
//Main function started
int main(){
 int *arr,n,i;
 while(1){
  //Taking the number of element
  printf("\nEnter the number of element you want to store:");
  scanf("%d",&n);
  if(n<=0){
   printf("\nAn array size must be a positive integer.");
   continue;
  }
  else
   break;
 }
 //Creating the array dynamically
 arr=(int*)malloc(n*sizeof(int));
 if(!arr) {
  printf("\nNot enough memory.");
  exit(0);
 }
 printf("\nEnter the element(s) in the array:");
 for(i=0;i<n;i++){
  printf("\nElement[%d]:",i+1);
  scanf("%d",&arr[i]);
 }
 printf("\nThe element(s) before sorting:");
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 printf("\nThe element(s) after sorting:");
 arr=quick_sort(arr,0,n-1);
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 return 0;
}

Output

Enter the number of element you want to store:7

Enter the element(s) in the array:
Element[1]:5

Element[2]:6

Element[3]:2

Element[4]:88

Element[5]:554

Element[6]:11

Element[7]:36

The element(s) before sorting: 5 6 2 88 554 11 36
The element(s) after sorting: 2 5 6 11 36 88 554

Selection Sort in C language

Selection Sort

This is a one kind of sorting technique. The complexity of this sorting technique is,
Worst-case performance : O(n^2)
Best-case performance : O(n^2)
Average-case performance : O(n^2)
For more details click here

Code

/*****Selection Sort*****/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//Function defination
int* selection_sort(int *arr,int *n){
 int i,j,temp;
 for(i=0;i<*n-1;i++)
  for(j=i+1;j<*n;j++)
   if(arr[i]>arr[j]){
    //Swapping
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
   }
 return arr;
}
//Starting the main function
int main(){
 int *arr,n,i;
 while(1){
  //Taking the number of element
  printf("\nEnter the number of element you want to store:");
  scanf("%d",&n);
  if(n<=0){
   printf("\nAn array size must be a positive integer.");
   continue;
  }
  else
   break;
 }
 //Create array dynamically
 arr=(int*)malloc(n*sizeof(int));
 if(!arr){
  printf("\nNot enough memory.");
  exit(0);
 }
 //Taking the element from user
 printf("\nEnter the element(s) in the array:");
 for(i=0;i<n;i++){
  printf("\nElement[%d]:",i+1);
  scanf("%d",&arr[i]);
 }
 //Print the array before sorting
 printf("\nThe element(s) before sorting:");
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 printf("\nThe element(s) after sorting:");
 //Call the sorting function
 arr=selection_sort(arr,&n);
 //Print the sorted array
 for(i=0;i<n;i++)
  printf(" %d",arr[i]);
 return 0;
}

Output

Enter the number of element you want to store:7

Enter the element(s) in the array:
Element[1]:2

Element[2]:4

Element[3]:1

Element[4]:5

Element[5]:8

Element[6]:7

Element[7]:3

The element(s) before sorting: 2 4 1 5 8 7 3
The element(s) after sorting: 1 2 3 4 5 7 8

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

Find Minimum In Stack In O(1) Time and O(1) Space

Find Minimum In Stack In O(1) Time and O(1) Space

For this problem I have used a stack of pointer to nodes. A node have two members one is the value part and another is the link to another node.

Conditions

• Update the minimum with each push operation
• A node (current) will point to another node if the current node have a previous minimum node else it will point to null
• During pop check the top node and the minimum node if they point to the same location then update the current minimum to previous minimum by assigning the link of the top node to minimum pointer
• If the top node has null to its link part then it is not the minimum node and no pointer manipulation needed,

Sample Operations

C++ Implementation

#include <iostream>
using namespace std;
#define MAX 9999

struct Node {
    int val;
    struct Node *add;
};

class Stack
{
    Node **arr, *minn;
    int s, top;

    public:
        Stack(int s) : s(s) {
            arr = new Node*[s];
            top = -1;
            minn = new Node();
            minn->val = MAX;
        }
        ~Stack() {
            delete [] arr;
        }

        void push(int item);
        int pop();
        int minimum() const {
            return (top ==-1)? -1 : minn->val;
        };
};

void Stack::push(int item) {
    if (top == s-1) {
        cout << "Stack full!" << endl;
    }
    else {
        Node *tmp = new Node();
        tmp->add = NULL;
        if (top == -1) {
            minn = tmp;
        }
        else {
            if (item <= minn->val) {
                tmp->add = minn;
                minn = tmp;
            }
        }
        tmp->val = item; ++top;
        arr[top] = tmp;
    }
}

int Stack::pop()
{
    int retVal = -1;
    if (top == -1) {
        delete minn;
        cout << "Stack empty!" << endl;
    }
    else {
        retVal = arr[top]->val;
        if (arr[top] == minn){
            minn = arr[top]->add;
        }
        top--;
    }
    return retVal;
}

int main()
{
    Stack s(6);
    s.push(7);
    s.push(1);
    s.push(1);
    s.push(2);
    s.push(4);
    s.push(0);
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    return 0;
}

Current Min: 0
Popped: 0
Current Min: 1
Popped: 4
Current Min: 1
Popped: 2
Current Min: 1
Popped: 1
Current Min: 1
Popped: 1
Current Min: 7
Popped: 7

Process returned 0 (0x0)   execution time : 0.044 s
Press any key to continue.

If you find anything wrong please comment below. And if you have any other approach then mail me at itsaboutcs@gmail.com.

Binary Insertion Sort

We can use binary search to reduce the number of comparisons in normal insertion sort. Binary Insertion Sort find use binary search to find the proper location to insert the selected item at each iteration. In normal insertion, sort it takes O(i) (at ith iteration) in worst case. we can reduce it to O(logi) by using binary search.

C Implementation

// Binary Insertion Sort
#include <stdio.h>
 
// A binary search based function to find the position
// where item should be inserted in a[low..high]
int binarySearch(int a[], int item, int low, int high)
{
    if (high <= low)
        return (item > a[low])?  (low + 1): low;
 
    int mid = (low + high)/2;
 
    if(item == a[mid])
        return mid+1;
 
    if(item > a[mid])
        return binarySearch(a, item, mid+1, high);
    return binarySearch(a, item, low, mid-1);
}
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
    int i, loc, j, k, selected;
 
    for (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted..
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space..
        while (j >= loc)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = selected;
    }
}
 
int main()
{
    int a[] = {37, 23, 0, 17, 12, 72, 31,
              46, 100, 88, 54};
    int n = sizeof(a)/sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
        printf("%d ",a[i]);
 
    return 0;
}

Output

Sorted array:
0 12 17 23 31 37 46 54 72 88 100

Kruskal's MST Algorithm

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph.
It works by growing forest. Kruskal's algorithm finds a safe edge to add to the growing forest by finding an edge with least weight that connects two tree in the forest.

Algorithm

# here + means union of twp sets
KRUSKAL(G):
  A = NULL
  foreach v in G.V:
  MAKE-SET(v)
  foreach (u, v) ordered by weight(u, v), increasing:
    if FIND-SET(u) != FIND-SET(v):
      A = A + {(u, v)}
      UNION(u, v)
  return A

C Implementation Using Disjoint Set Data Structure

/* Kruskals MST Algorithm Implemented Using Disjoint Set Data Structure (Union & Find).....
 * Where Graph Is Represented In Adjacency Matrix Structure "AdjMa".....
 * Each Cell Has Two Members weight and visited.....
 * For Sorting The Edges WRT Its Weight A Edge: Structure Is Considered.....
 * Where 'u' & 'v' are each end of a vertex with corresponding 'weight'......
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE 1
#define FALSE 0
#define N 4
#define INF 9999

typedef struct
{
    int weight;
    int visited;
}AdjMatrix;

typedef struct
{
    int weight;
    int u;
    int v;
}Edge;

void takeInput(AdjMatrix graph[][N])
{
    int i,j;
    printf("Enter The Matrix:\n");

for(i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            scanf("%d",&graph[i][j].weight);
            if(graph[i][j].weight == 0) graph[i][j].weight = INF;
            graph[i][j].visited = FALSE;
        }
    }
}

void printGraph(AdjMatrix graph[][N])
{
    int i,j;
    for(i = 0; i < N; i++)
    {
        putchar('[');
        for (j = 0; j < N; j++)
        {   if(graph[i][j].weight == INF)
                printf("%3d ",0);
            else
                printf("%3d ",graph[i][j].weight);
        }
        putchar(']');
        putchar('\n');
    }
}

int find(int set[], int i)
{

    if (set[i] == -1)
        return i;
    else
        return find(set, set[i]);
}

//Function to union two sets...
void Union(int set[], int u, int v)
{
    int uset = find(set, u);
    int vset = find(set, v);
    set[uset] = vset;
}

//A comparison function for built-in qsort()...
int myComp(const void* a, const void* b)
{
    Edge *a1 = (Edge *)a;
    Edge *b1 = (Edge *)b;

    if (a1->weight > b1->weight)
        return 1;
    else
        return -1;
}

//Function for finding MST using Kruskal's Algorithm....
void kruskalMST(AdjMatrix graph[][N])
{
    int i, j, k=0, x, y, set[20], cost = 0, e=0;
    AdjMatrix tree[N][N];
    Edge edge[20];

    //Picking The Edges...
    for(i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            tree[i][j].weight = 0;
            if(graph[i][j].visited != TRUE)
            {
                edge[k].weight = graph[i][j].weight;
                edge[k].u = i;
                edge[k++].v = j;
                graph[j][i].visited = TRUE;

            }
        }
    }

    //Sorting the edges using quicksort()....
    qsort(edge, k, sizeof(Edge), myComp);

    //Setting all elements of parent = -1
    //each element of parent is a disjoint set..
    memset(set, -1, N * sizeof(set[0]));

    i = 0;
    //Loops untill all vertices are considered that is e = #(vertices) - 1
    while (e < N - 1)
    {
        x = find(set, edge[i].u);
        y = find(set, edge[i].v);

        if (x != y)
        {
            cost = cost + edge[i].weight;
            tree[x][y].weight = edge[i].weight;
            tree[y][x].weight = edge[i].weight;
            Union(set, x, y);
            e++;
        }
        i++;
    }

    puts("\nAdjMatrix For MST:\n");
    printGraph(tree);
    printf("\n\nMST Cost = %d",cost);
}


int main()
{
    AdjMatrix graph[N][N];
    system("cls");
    takeInput(graph);
    printf("\nGiven Graph In AdjMatrix Representation:\n");
    printGraph(graph);
    kruskalMST(graph);
    return 0;
}

Output

Enter The Matrix:
0 7 5 2
7 0 4 3
5 4 0 1
2 3 1 0

Given Graph In AdjMatrix Representation:
[  0   7   5   2 ]
[  7   0   4   3 ]
[  5   4   0   1 ]
[  2   3   1   0 ]

AdjMatrix For MST:
[  0   0   0   2 ]
[  0   0   0   3 ]
[  0   0   0   1 ]
[  2   3   1   0 ]

MST Cost = 6
--------------------------------
Process exited after 50.48 seconds with return value 0
Press any key to continue . . .

Discussion

• Time Complexity: Time complexity of Kruskals algorithm depends on how we implement each operation like cycle detection and union and sorting etc
• It can be shown to run in O(ElogE) time or equivalently O(ElogV)
• It can be shown to run in O(ElogE) time or equivalently O(ElogV)
• WE can use Union-Find for cycle detection to keep track of which vertices are in which component, Which has at most e iterations. Union Find by rank or path compression take O(log(v)) time.
  • Total = O(ElogE + ElogV) = O(Elog E) or O(ElogV)