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