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