Manoj Patra's Blog: August 2017

Thursday, August 17, 2017

Program to Implement Merge Sort in C

#include<stdio.h>
void mergesort(int arr[], int i, int j);
void merge(int arr[], int i1, int j1, int i2, int j2);
int main()
{
   int arr[100], n, i, j;
   printf("\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -");
   printf("\n= = = = = = = = = = = Merge Sort in C = = = = = = = = = = = =");
   printf("\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n");
   printf("How many integers you wanna store..? : ");
   scanf("%d",&n);
   printf("Enter %d integers into the array:\n", n);
   for(i=0; i<n; i++)
   {
       scanf(" %d",&arr[i]);
   }
   printf("Before sorting the array elements are:\n");
   for(j=0; j<n; j++)
   {
       printf("%d\t", arr[j]);
   }

   mergesort(arr,0,n-1);

   printf("\n\nAfter sorting the array elements are:\n");
   for(i=0; i<n; i++)
   {
       printf("%d\t",arr[i]);
   }
   printf("\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =\n\n");
   return 0;
}

void mergesort(int arr[],int p,int q)
{
   int mid;

   if(p<q)
   {
       mid=(p+q)/2;
       mergesort(arr,p,mid);
       mergesort(arr,mid+1,q);
       merge(arr,p,mid,mid+1,q);
   }
}

void merge(int arr[], int i1, int j1, int i2, int j2)
{
   int temp[100];
   int i,j,k;
   i=i1;
   j=i2;
   k=0;
   while(i<=j1 && j<=j2)
   {
       if(arr[i]<arr[j])
       {
           temp[k]=arr[i];
           i++;
       }
       else
       {
           temp[k]=arr[j];
           j++;
       }
       k++;
   }
   while(i<=j1)
   {
       temp[k]=arr[i];
       k++;
       i++;
   }
   while(j<=j2)
   {
       temp[k]=arr[j];
       k++;
       j++;
   }
   for(i=i1,j=0; i<=j2; i++,j++)
       arr[i]=temp[j];
}

OutPut:
manoj@ubuntu:~/cp$ gcc merge_sort.c -o merge_sort
manoj@ubuntu:~/cp$ ./merge_sort

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
= = = = = = = = = = = Merge Sort in C = = = = = = = = = = = =
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
How many integers you wanna store..? : 7
Enter 7 integers into the array:
4
5
35
2
5
1
35
Before sorting the array elements are:
4   5   35   2   5   1   35

After sorting the array elements are:
1   2   4   5   5   35   35
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

manoj@ubuntu:~/cp$

Quick Sort by taking middle element as pivot in C

#include<stdio.h>
void quick_sort_mid(int a[], int k, int l);
int partition(int a[], int k, int l);
int main()
{
   int arr[100], n, i, j;
   printf("\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -");
   printf("\n= = = = = Quick Sort by taking middle element as pivot in C = = = = =\n");
   printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n");
   printf("How many integers you wanna store..? : ");
   scanf("%d",&n);
   printf("Enter %d integers into the array:\n", n);
   for(i=0; i<n; i++)
   {
       scanf(" %d",&arr[i]);
   }
   printf("Before sorting the array elements are:\n");
   for(j=0; j<n; j++)
   {
       printf("%d\t", arr[j]);
   }

   quick_sort_mid(arr,0,n-1);

   printf("\n\nAfter sorting the array elements are:\n");
   for(i=0; i<n; i++)
   {
       printf("%d\t",arr[i]);
   }
   printf("\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =\n\n");
   return 0;
}

void quick_sort_mid(int arr[], int k, int l)
{
   if(k<l)
   {
       int p;
       p=partition(arr,k,l);
       quick_sort_mid(arr, k, p-1);
       quick_sort_mid(arr, p+1, l);
   }
}

int partition(int arr[], int m, int n)
{
   int i, j, temp, pivot;
   i=m;
   j=n;
   pivot=(m+n)/2;
   while(i<j)
   {
       while(arr[i]<=arr[pivot] && i<pivot)
       {
           i++;
       }
       while(arr[j]>=arr[pivot] && j>pivot)
       {
           j--;
       }
       if(i!=pivot && j!=pivot)
       {
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
       }
       else if(i<pivot && j==pivot)
       {
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
           pivot=i;
       }
       else if(j>pivot && i==pivot)
       {
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
           pivot=j;
       }
   }
   return pivot;
}

OutPut:
manoj@ubuntu:~/cp$ gcc quicksort_mid.c -o quicksort_mid
manoj@ubuntu:~/cp$ ./quicksort_mid

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
= = = = = Quick Sort by taking middle element as pivot in C = = = = =
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
How many integers you wanna store..? : 7
Enter 7 integers into the array:
4
7
5
7
6
7
2
Before sorting the array elements are:
4   7   5   7   6   7   2

After sorting the array elements are:
2   4   5   6   7   7   7
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

manoj@ubuntu:~/cp$

Quick Sort by taking last element as pivot in C

Quick Sort by taking first element as pivot in C

Friday, August 4, 2017

Program to implement Quick Sort in C

#include<stdio.h>
void quick_sort_end(int a[], int k, int l);
int partition(int a[], int k, int l);
int main()
{
   int arr[100], n, i, j;
   printf("\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -");
   printf("\n= = = = = Quick Sort by taking first element as pivot in C = = = = =\n");
   printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n");
   printf("How many integers you wanna store..? : ");
   scanf("%d",&n);
   printf("Enter %d integers into the array:\n", n);
   for(i=0; i<n; i++)
   {
       scanf(" %d",&arr[i]);
   }
   printf("Before sorting the array elements are:\n");
   for(j=0; j<n; j++)
   {
      printf("%d\t", arr[j]);
   }

   quick_sort_end(arr,0,n-1);

   printf("\n\nAfter sorting the array elements are:\n");
   for(i=0; i<n; i++)
   {
       printf("%d\t",arr[i]);
   }
   printf("\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =\n\n");
   return 0;
}

void quick_sort_end(int arr[], int k, int l)
{
   if(k<l)
   {
       int p;
       p=partition(arr,k,l);
       quick_sort_end(arr, k, p-1);
       quick_sort_end(arr, p+1, l);
   }
}

int partition(int arr[], int m, int n)
{

   int i, j, temp, pivot;
   i=n+1;
   pivot=m;
   for(j=n; j>=m; j--)
   {
       if(arr[j]>=arr[pivot])
       {
           i--;
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
       }
   }
   return i;
}

OutPut:
manoj@ubuntu:~/cp$ gcc quicksort_beg.c -o quicksort_beg
manoj@ubuntu:~/cp$ ./quicksort_beg

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
= = = = = Quick Sort by taking first element as pivot in C = = = = =
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
How many integers you wanna store..? : 8
Enter 8 integers into the array:
2
6
7
3
5
4
8
1
Before sorting the array elements are:
2    6    7    3    5    4    8    1

After sorting the array elements are:
1    2    3    4    5    6    7    8
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

manoj@ubuntu:~/cp$
####
#include<stdio.h>
void quick_sort_end(int a[], int k, int l);
int partition(int a[], int k, int l);
int main()
{
    int arr[100], n, i, j;
    printf("\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -");
    printf("\n= = = = = Quick Sort by taking last element as pivot in C = = = = =\n");
    printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n");
    printf("How many integers you wanna store..? : ");
    scanf("%d",&n);
    printf("Enter %d integers into the array:\n", n);
    for(i=0; i<n; i++)
    {
       scanf(" %d",&arr[i]);
    }
    printf("Before sorting the array elements are:\n");
    for(j=0; j<n; j++)
    {
        printf("%d\t", arr[j]);
    }

    quick_sort_end(arr,0,n-1);

    printf("\n\nAfter sorting the array elements are:\n");
    for(i=0; i<n; i++)
    {
       printf("%d\t",arr[i]);
    }
    printf("\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =\n\n");
    return 0;
}

void quick_sort_end(int arr[], int k, int l)
{
    if(k<l)
    {
       int p;
       p=partition(arr,k,l);
       quick_sort_end(arr, k, p-1);
       quick_sort_end(arr, p+1, l);
    }
}

int partition(int arr[], int m, int n)
{
    int i, j, temp, pivot;
    i=m-1;
    pivot=n;
    for(j=m; j<=n; j++)
    {
       if(arr[j]<=arr[pivot])
       {
           i++;
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
       }
    }
    return i;
}

OutPut:
manoj@ubuntu:~/cp$ gcc quicksort_end.c -o quicksort_end
manoj@ubuntu:~/cp$ ./quicksort_end

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
= = = = = Quick Sort by taking last element as pivot in C = = = = =
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
How many integers you wanna store..? : 8
Enter 8 integers into the array:
2
6
7
3
5
4
8
1
Before sorting the array elements are:
2   6   7   3   5   4   8   1

After sorting the array elements are:
1   2   3   4   5   6   7   8
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

manoj@ubuntu:~/cp$
####

#include<stdio.h>
void quick_sort_mid(int a[], int k, int l);
int partition(int a[], int k, int l);
int main()
{
   int arr[100], n, i, j;
   printf("\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -");
   printf("\n= = = = = Quick Sort by taking middle element as pivot in C = = = = =\n");
   printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n");
   printf("How many integers you wanna store..? : ");
   scanf("%d",&n);
   printf("Enter %d integers into the array:\n", n);
   for(i=0; i<n; i++)
   {
       scanf(" %d",&arr[i]);
   }
   printf("Before sorting the array elements are:\n");
   for(j=0; j<n; j++)
   {
       printf("%d\t", arr[j]);
   }

   quick_sort_mid(arr,0,n-1);

   printf("\n\nAfter sorting the array elements are:\n");
   for(i=0; i<n; i++)
   {
       printf("%d\t",arr[i]);
   }
   printf("\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =\n\n");
   return 0;
}

void quick_sort_mid(int arr[], int k, int l)
{
   if(k<l)
   {
       int p;
       p=partition(arr,k,l);
       quick_sort_mid(arr, k, p-1);
       quick_sort_mid(arr, p+1, l);
   }
}

int partition(int arr[], int m, int n)
{
   int i, j, temp, pivot;
   i=m;
   j=n;
   pivot=(m+n)/2;
   while(i<j)
   {
       while(arr[i]<=arr[pivot] && i<pivot)
       {
           i++;
       }
       while(arr[j]>=arr[pivot] && j>pivot)
       {
           j--;
       }
       if(i!=pivot && j!=pivot)
       {
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
       }
       else if(i<pivot && j==pivot)
       {
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
           pivot=i;
       }
       else if(j>pivot && i==pivot)
       {
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
           pivot=j;
       }
   }
   return pivot;
}

OutPut:
manoj@ubuntu:~/cp$ gcc quicksort_mid.c -o quicksort_mid
manoj@ubuntu:~/cp$ ./quicksort_mid

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
= = = = = Quick Sort by taking middle element as pivot in C = = = = =
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
How many integers you wanna store..? : 7
Enter 7 integers into the array:
4
7
5
7
6
7
2
Before sorting the array elements are:
4   7   5   7   6   7   2

After sorting the array elements are:
2   4   5   6   7   7   7
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

manoj@ubuntu:~/cp$

Program to implement Insertion Sort in C

#include<stdio.h>
void insertion_sort(int [], int k);
int main()
{
   int arr[100], n, i, j;
   printf("\n= = = = = = = = = = Insertion Sort in C = = = = = = = = = =\n");
   printf("How many integers you wanna store..? : ");
   scanf("%d",&n);
   printf("Enter %d integers into the array:\n", n);
   for(i=0; i<n; i++)
   {
       scanf(" %d",&arr[i]);
   }
   printf("Before sorting the array elements are:\n");
   for(j=0; j<n; j++)
   {
      printf("%d\t", arr[j]);
   }

   insertion_sort(arr,n);

   printf("\n\nAfter sorting the array elements are:\n");
   for(i=0; i<n; i++)
   {
       printf("%d\t",arr[i]);
   }
   printf("\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =\n\n");
   return 0;
}

void insertion_sort(int arr[], int k)
{

   int i, j, temp;
   for(i=1; i<k; i++)
   {
       temp=arr[i];
       j=i-1;
       while((j>=0) && (arr[j]>temp))
       {
           arr[j+1]=arr[j];
           j--;
       }
       arr[j+1]=temp;
   }
}

OutPut:
manoj@ubuntu:~/cp$ gcc insertionsort.c -o insertionsort
manoj@ubuntu:~/cp$ ./insertionsort

= = = = = = = = = = Insertion Sort in C = = = = = = = = = =
How many integers you wanna store..? : 8
Enter 8 integers into the array:
2
6
7
3
5
4
8
1
Before sorting the array elements are:
2    6    7    3    5    4    8    1

After sorting the array elements are:
1    2    3    4    5    6    7    8
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

manoj@ubuntu:~/cp$

Program to implement Bubble Sort in C

#include <stdio.h>
void bubble_sort(int a[], int k);
int main()
{
   int arr[100], n, i;
   printf("\n= = = = = = = = = = Bubble Sort in C = = = = = = = = = =\n");
   printf("How many integers you wanna store..? : ");
   scanf("%d", &n);
   printf("Enter %d integers into the array:\n", n);
   for(i=0; i<n; i++)
   {
       scanf("%d",&arr[i]);
   }
   printf("Before sorting the array elements are:\n");
   for(i=0; i<n; i++)
   {
       printf("%d\t",arr[i]);
   }

   bubble_sort(arr,n);

   printf("\n\nAfter sorting the array elements are:\n");
   for(i=0; i<n; i++)
   {
       printf("%d\t",arr[i]);
   }
   printf("\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =\n\n");
   return 0;
}

void bubble_sort(int arr[], int k)
{
   int i, j, temp;
   for(i=0; i<k-1; i++ )
   {
       for(j=0; j<k-i-1; j++ )
       {
           if(arr[j] > arr[j+1])
           {
               temp = arr[j];
               arr[j] = arr[j+1];
               arr[j+1] = temp;
           }
       }
   }
}
OutPut:
manoj@ubuntu:~/cp$ gcc bubblesort.c -o bubblesort
manoj@ubuntu:~/cp$ ./bubblesort

= = = = = = = = = = Bubble Sort in C = = = = = = = = = =
How many integers you wanna store..? : 8
Enter 8 integers into the array:
4
7
6
3
5
2
8
1
Before sorting the array elements are:
4    7    6    3    5    2    8    1

After sorting the array elements are:
1    2    3    4    5    6    7    8
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

manoj@ubuntu:~/cp$

Program to implement Selection Sort in C

#include <stdio.h>
void selection_sort(int a[], int k);
int main()
{
   int arr[100], n, i;
   printf("\n= = = = = = = = = = Selection Sort in C = = = = = = = = = =\n");
   printf("How many integers you wanna store..? : ");
   scanf("%d", &n);
   printf("Enter %d integers into the array:\n", n);
   for(i=0; i<n; i++)
   {
       scanf("%d",&arr[i]);
   }
   printf("Before sorting the array elements are:\n");
   for(i=0; i<n; i++)
   {
       printf("%d\t",arr[i]);
   }
   selection_sort(arr,n);
   printf("\n\nAfter sorting the array elements are:\n");
   for(i=0; i<n; i++)
   {
       printf("%d\t",arr[i]);
   }
   printf("\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =\n\n");
   return 0;
}
void selection_sort(int arr[], int k)
{
   int i, j, pos, temp;
   for (i=0; i<(k-1); i++ )
   {
       pos=i;
       for (j=i+1; j<k;j++ )
       {
           if(arr[pos]>arr[j] )
               pos=j;
       }
       if(pos!=i)
       {
           temp = arr[i];
           arr[i] = arr[pos];
           arr[pos] = temp;
       }
   }

}

OutPut:
manoj@ubuntu:~/cp$ gcc select_sort.c -o select_sort
manoj@ubuntu:~/cp$ ./select_sort

= = = = = = = = = = Selection Sort in C = = = = = = = = = =
How many integers you wanna store..? : 8
Enter 8 integers into the array:
4
7
6
3
5
2
8
1
Before sorting the array elements are:
4    7    6    3    5    2    8    1

After sorting the array elements are:
1    2    3    4    5    6    7    8
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

manoj@ubuntu:~/cp$