Merge Sort

Merge Sort- based On Divide and Conquer algorithm

 In Merge sort algorithm the given array is divided  into two parts and again merge with proper order.
1.Given array is divided into left and right half till we get two element in left half recursively.
2.After getting two element in left half call merge function it will first split array into single element namely left array and right array.
3.Then merge these two array using ascending order of left and right array.
4.Now move to right part of previous array,here also same procedure split array into left and right then merge.

Recursive Function:
Function call within same function is called recursive function.

Whenever function call occur within program the current value of the variables are push onto stack and pop again while returning the function call.
Hence here the index of array change according to function call and recursively left-right-merge is done.



Library files

#include<stdlib.h>
#include<stdio.h>
//Function Prototypes:
void merge(int arr[], int l, int m, int r,int arr_size);
void mergeSort(int arr[], int l, int r,int arr_size);
void printArray(int A[],int arr_size);
int y=0;//Counter for counting merge operation

int main()
{
    int arr[] = {35,25,48,4,8,72,13,100};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printf("Given array is \n");
    printArray(arr,arr_size);
    mergeSort(arr, 0, arr_size - 1,arr_size);
    printf("\nSorted array is \n");
    printArray(arr,arr_size);
    return 0;
}

// l is for left index and r is right index of the sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r,int arr_size)
{
    if (l < r)
    {
        int m = l+(r-l)/2;
        mergeSort(arr, l, m,arr_size);// Recursive function call will execute till we get atleast two element in array
        mergeSort(arr, m+1, r,arr_size);// Recursive function call will execute till we get atleast two element in array

        merge(arr, l, m, r,arr_size);//this function will split array into two part and again merge with ascending order
    }
 }

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r,int arr_size)
{
y++;
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    //create temp arrays
    int L[n1], R[n2];
    //Copy data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
    // Merge the temp arrays back into arr[l..r]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray

    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }

    printf("\n array after %d times merge (merge function)\n",y);
    printArray(arr,arr_size);
}

void printArray(int A[], int arr_size)
{
    int i;
    for (i=0; i <= arr_size-1; i++)
    printf("\'%d\'\t ", A[i]);
    printf("\n");
}


/*
Output
Given array is
'35' '25' '48' '4' '8' '72' '13' '100'

 array after 1 times merge (merge function)
'25' '35' '48' '4' '8' '72' '13' '100'

 array after 2 times merge (merge function)
'25' '35' '4' '48' '8' '72' '13' '100'

 array after 3 times merge (merge function)
'4' '25' '35' '48' '8' '72' '13' '100'

 array after 4 times merge (merge function)
'4' '25' '35' '48' '8' '72' '13' '100'

 array after 5 times merge (merge function)
'4' '25' '35' '48' '8' '72' '13' '100'

 array after 6 times merge (merge function)
'4' '25' '35' '48' '8' '13' '72' '100'

 array after 7 times merge (merge function)
'4' '8' '13' '25' '35' '48' '72' '100'

Sorted array is
'4' '8' '13' '25' '35' '48' '72' '100'




*/

Insertion Sort

Best case complexity of insertion sort is O(n), average and the worst case complexity is O(n²).

Working of Insertion Sort:
Insertion sort work same as player of playing card places upcoming card at its proper sequence.

• Start from pointing first and second element in an array.
• If second element of array is lesser than first element then swap position of those two element.
• Increment the pointer and check for all element sequentially and place each upcoming element to proper sequence in an array till last element of array.

Entered Array is :'111' '12'    '45'    '13'    '78'    '80'
 Sorted Array after 1 pass:'12' '111'   '45'    '13'    '78'    '80'
 Sorted Array after 2 pass:'12' '45'    '111'   '13'    '78'    '80'
 Sorted Array after 3 pass:'12' '13'    '45'    '111'   '78'    '80'
 Sorted Array after 4 pass:'12' '13'    '45'    '78'    '111'   '80'

 Sorted Array after 5 pass:'12' '13'    '45'    '78'    '80'    '111'    

library declaration:
 #include<stdio.h>
#include<stdlib.h>

Prototype Declaration:
int insertionsort(int*,int);
void display(int* ,int);

Main Program:
int main()
{
    int *arr,i,n;
    printf("Enter the no. of elements\n");
    scanf("%d",&n);
    arr=(int*)malloc(n*sizeof(int));
    printf("Enter elements\n");
    for(i=0;i<n;i++)
        scanf("%d \t",(arr+i));
printf("\nEntered Array is :");
display(arr,n);
insertionsort(arr,n);
printf("\nFinally sorted Array is :");
display(arr,n);
return 0;
}

C Function For Insertion Sort:
int insertionsort(int *arr,int n)
{
    int i,j,temp;
for(i=1;i<n;i++)
    {
        temp=*(arr+i);
        j=i-1;
        while(temp<*(arr+j)&&j>=0)
        {
            *(arr+(j+1))=*(arr+j);
            j--;
        }
        *(arr+(j+1))=temp;
        printf("\n Sorted Array after %d pass:",i);
        display(arr,n);
     }
    return 0;
}

C Function For Display Array:
void display(int *arr,int n)
{ int i=0;
  for(i=0;i<n;i++)
printf("\'%d\'\t",*(arr+i));
}

Implementation of Queue using Link List Functions

Implementation of Queue using Link List Functions

Function to Create an empty queue

create only pointer pointing to NULL

void create()

{

    front = rear = NULL;

}

Function for getting queue size 

Take a global variable count and display here.

At every time of enqueue increment count.

and in  dequeue function decrement count.

void queuesize()

{

    printf("\n Queue size : \'%d\'", count);

}

Function for Enqueing the queue

Add a node with Null pointer at rear side and update rear to new node.

void enq(int data)

{

    if (rear == NULL)

    {

        rear = (struct node *)malloc(1*sizeof(struct node));

        rear->ptr = NULL;

        rear->info = data;

        front = rear;

    }

    else

    {

        temp=(struct node *)malloc(1*sizeof(struct node));

        rear->ptr = temp;

        temp->info = data;

        temp->ptr = NULL;

        rear = temp;

    }

    count++; //count for counting number of nodes

}

Function for Displaying the queue elements

void display()

{

    front1 = front;

    if ((front1 == NULL) && (rear == NULL))

    {

        printf("Queue is empty");

        return;

    }

    while (front1 != rear)

    {

        printf("\'%d\' ", front1->info);

        front1 = front1->ptr;

    }

    if (front1 == rear)

        printf("\'%d\'", front1->info);

}

Function for Dequeing the queue

Update front pointer to next location and Remove old front element using dummy pointer as front1. 

void deq()

{

    front1 = front;

    if (front1 == NULL)

    {

        printf("\n Error: Trying to display elements from empty queue");

        return;

    }

    else

        if (front1->ptr != NULL)

        {

            front1 = front1->ptr;

            printf("\n Dequed value : %d", front->info);

            free(front);

            front = front1;

        }

        else

        {

            printf("\n Dequed value : %d", front->info);

            free(front);

            front = NULL;

            rear = NULL;

        }

        count--; // decrement count of total nodes

}

Function to display front element of queue

int frontelement()

{

    if ((front != NULL) && (rear != NULL))

        return(front->info);

    else

        return 0;

}

Function for Display if queue is empty or not

If front and rear both are pointing to Null then queue is empty.

void empty()

{

     if ((front == NULL) && (rear == NULL))

        printf("\n Queue empty");

    else

       printf("Queue not empty");

}

/*

Output

1-Enque                                                                                                                       

 2 - Deque                                                                                                                      

 3 - Front element                                                                                                               

 4 - Empty                                                                                                                      

 5 - Display                                                                                                                     

 6 - Queuesize                                                                                                                  

 7 - Exit                                                                                                                        

 Enter choice : 1                                                                                                               

Enter data for Enque: 10                                                                                                         

                                                                                                                                

 Element of Queue after Enqueque operation:'10'                                                                                  

 Enter choice : 1                                                                                                               

Enter data for Enque: 20                                                                                                         

                                                                                                                                

 Element of Queue after Enqueque operation:'10' '20'                                                                             

 Enter choice : 1                                                                                                               

Enter data for Enque:                                                                                                            

30                                                                                                                              

                                                                                                                                 

 Element of Queue after Enqueque operation:'10' '20' '30'                                                                       

 Enter choice : 2

 Dequed value : 10                                                                                                              

 Element of Queue after deque operation:'20' '30'                                                                                

 Enter choice : 3                                                                                                               

Front element : 20                                                                                                               

 Enter choice : 4                                                                                                               

Queue not empty                                                                                                                  

 Enter choice : 5                                                                                                               

'20' '30'                                                                                                                        

 Enter choice : 6                                                                                                               

                                                                                                                                 

 Queue size : '2'                                                                                                               

 Enter choice : 7                                                                                                                

                                                                                                                                

                                                                                                                                 

...Program finished with exit code 0                                                                                            

Press ENTER to exit console. 

           

*/

Implementation of Queue using Link List (Menu driven Program)

Queue is linear data structure which operates on particular order of operation such as First in First out(FIFO).

Example: 

Line of student at admission counter, line of people at ATM machine etc

Pointer used for queue:
front-point to first arrived i.e. oldest element
rear-point to last arrived i.e.latest element 

Main operations

Enqueue:

Add element into queue at rear side, at every new arrival of element rear will point to latest arrivel element .

Dequeue:

Delete element of queue at front side,front will updated to next of front ,use dummy pointer for this operstion.

Node Structure:

struct node
{
    int info;
    struct node *ptr;
}*front,*rear,*temp,*front1;

Functions used in this program:

int frontelement();

void enq(int data);

void deq();

void empty();

void display();

void create();

void queuesize();

Menu Driven Program:

int no, ch, e;
    printf("\n 1 - Enque");
    printf("\n 2 - Deque");
    printf("\n 3 - Front element");
    printf("\n 4 - Empty");
    printf("\n 5 - Display");
    printf("\n 6 - Queuesize");
    printf("\n 7 - Exit");
    create();
    while (1)
    {
        printf("\n Enter choice : ");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1:
            printf("Enter data for Enque: ");
            scanf("%d", &no);
            enq(no);
                        printf("\n Element of Queue after Enqueque operation:");
                        display();
           
            break;
        case 2:
            deq();
            printf("\n Element of Queue after deque operation:");
                        display();
            break;
        case 3:
            e = frontelement();
            if (e != 0)
                printf("Front element : %d", e);
            else
                printf("\n No front element in Queue as queue is empty");
            break;
        case 4:
            empty();
            break;
        case 5:
        display();
            break;
          
        case 6: queuesize();
            break;
           
        case 7:
            exit(0);
        default:
            printf("Wrong choice, Please enter correct choice  ");
            break;
        }
    }
}

C code for Bubble Sort Algorithm

Logic:
Bubble sort algorithm used for sorting purpose.
Two pointer used to point first and second position of element.
Each element is compared with next element.
If next element is smaller than previous then swapping operation is done and both pointer incremented by 1.
 Complexity- Average case complexity O(n^2)
Best case O(n)

 // C program for implementation of Bubble sort 

#include <stdio.h> 

void swap(int *xp, int *yp); 
void bubbleSort(int arr[], int n) ;
void printArray(int arr[], int size);  

int main() 
{ int arr[10],n,i;

printf("\n Enter number of element in random array:");
scanf("%d",&n);

printf("\n Enter element of array :");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("\n Entered array is :");
printArray(arr,n);

// int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
// int n = sizeof(arr)/sizeof(arr[0]); 
bubbleSort(arr, n); 
printf("\nSorted array: \n"); 
printArray(arr, n); 
return 0; 
}

/* Function to print an array */
void printArray(int arr[], int size) 
{ 
int i; 
for (i=0; i < size; i++) 
printf(" \'%d\' ", arr[i]); 
// printf("\n"); 
}


// A function to implement bubble sort 
void bubbleSort(int arr[], int n) 
{ 
int i, j; 
for (i = 0; i < n-1; i++)  

  for (j = 0; j < n-i-1; j++) 
{ if (arr[j] > arr[j+1]) 
swap(&arr[j], &arr[j+1]); 
printf("\n Element of array at  \'%d\' iteration\'%d\' pass\t:",i,j);
printArray(arr,n);

printf("\t Swap %d with %d",arr[j],arr[j+1]);
}

} 

void swap(int *xp, int *yp) 
{ 
int temp = *xp; 
*xp = *yp; 
*yp = temp; 
} 

/*
Output
 Enter number of element in random array:
 Enter element of array :
 Entered array is : '6'  '5'  '4'  '3'  '2' 
 Element of array at  '0' iteration'0' pass : '5'  '6'  '4'  '3'  '2' Swap 5 with 6
 Element of array at  '0' iteration'1' pass : '5'  '4'  '6'  '3'  '2' Swap 4 with 6
 Element of array at  '0' iteration'2' pass : '5'  '4'  '3'  '6'  '2' Swap 3 with 6
 Element of array at  '0' iteration'3' pass : '5'  '4'  '3'  '2'  '6' Swap 2 with 6
 Element of array at  '1' iteration'0' pass : '4'  '5'  '3'  '2'  '6' Swap 4 with 5
 Element of array at  '1' iteration'1' pass : '4'  '3'  '5'  '2'  '6' Swap 3 with 5
 Element of array at  '1' iteration'2' pass : '4'  '3'  '2'  '5'  '6' Swap 2 with 5
 Element of array at  '2' iteration'0' pass : '3'  '4'  '2'  '5'  '6' Swap 3 with 4
 Element of array at  '2' iteration'1' pass : '3'  '2'  '4'  '5'  '6' Swap 2 with 4
 Element of array at  '3' iteration'0' pass : '2'  '3'  '4'  '5'  '6' Swap 2 with 3
Sorted array: 
 '2'  '3'  '4'  '5'  '6' 
*/