Algorithms :
- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort
- Merge Sort
- Heap Sort
Q1. Bubble Sort Algorithm.
Ans. Using C
// c program for bubble sort
#include<stdio.h>
#include<conio.h>
void bubble_sort(int *,int);
void display(int *,int);
int main()
{
int arr[10],n,i;
printf("\n\t\t\t\t\t[ BUBBLE SORTING ]\n");
printf("\n Type limit >>| ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\tElement %d >>| ",i+1);
scanf("%d",&arr[i]);
}
printf("\n Before sorting.... >> ");
display(arr,n);
bubble_sort(arr,n);
printf("\n\n After sorting.... >> ");
display(arr,n);
getch();
return 0;
}
void bubble_sort(int arr[],int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(arr[j] > arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
void display(int arr[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf(" %d",arr[i]);
}
}
Ans. Using C++
// cpp program for bubble sort
#include<iostream>
#include<conio.h>
using namespace std;
void bubble_sort(int *,int);
void display(int *,int);
int main()
{
int arr[100],n;
cout<<"\n\t\t\t\t\t[ BUBBLE SORTING ]\n";
cout<<"\n Enter limit >>| ";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"\tElement "<<i+1<<" >>| ";
cin>>arr[i];
}
cout<<"\n Before sorting.... >> ";
display(arr,n);
bubble_sort(arr,n);
cout<<"\n\n After sorting.... >> ";
display(arr,n);
getch();
return 0;
}
void bubble_sort(int arr[],int n)
{
for(int i=1;i<n;i++)
{
for(int j=0;j<n-i;j++)
{
int temp;
if(arr[j] > arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
void display(int arr[],int n)
{
for(int i=0;i<n;i++)
{
cout<<" "<<arr[i];
}
}
Try and run :
// Try and run.
Q2. Selection Sort Algorithm.
Ans. Using C
// c program for selection sort
#include<stdio.h>
#include<conio.h>
void display(int *,int);
void selection_sort(int *,int);
int main()
{
int n,ele[10],i;
printf("\n\t\t\t\t\t[ SELECTION SORTING ]\n");
printf("\n Enter array limit >>| ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\tEnter element %d >>| ",i+1);
scanf("%d",&ele[i]);
}
printf("\n Before Sorting... ");
display(ele,n);
selection_sort(ele,n);
printf("\n After Sorting... ");
display(ele,n);
getch();
return 0;
}
void display(int a[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf(" %d",a[i]);
}
}
void selection_sort(int a[],int n)
{
int temp,i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
Ans. Using C++
// cpp program for selection sort
#include<iostream>
#include<conio.h>
using namespace std;
void display(int *,int);
void selection_sort(int *,int);
int main()
{
int n,ele[10];
cout<<"\n\t\t\t\t\t[ SELECTION SORTING ]\n";
cout<<"\n Enter limit of elements >>| ";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<" Enter element "<<i+1<<" >>| ";
cin>>ele[i];
}
cout<<"\n Before Sorting..."<<endl;
display(ele,n);
selection_sort(ele,n);
cout<<"\n After Sorting..."<<endl;
display(ele,n);
getch();
return 0;
}
void display(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<" "<<a[i];
}
}
void selection_sort(int a[],int n)
{
int temp;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
Try and run :
// Try and run.
Q3. Insertion Sort Algorithm.
Ans. Using C
// c program for insertion sort
#include<stdio.h>
#include<conio.h>
void insertion_sort(int *,int);
void display(int *,int);
int main()
{
int n,ele[10],i;
printf("\n\t\t\t\t\t[ INSERTION SORT ]\n");
printf(" Enter limit >>| ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\tEnter element %d >>| ",i+1);
scanf("%d",&ele[i]);
}
printf("\n\n Before Sorting >>| ");
display(ele,n);
insertion_sort(ele,n);
printf("\n After Sorting >>| ");
display(ele,n);
getch();
return 0;
}
void insertion_sort(int *a,int n)
{
int key,j,i;
for(i=1;i<n;i++)
{
key=a[i];
j=i-1;
while((a[j] > key)&&(j > -1))
{
a[j+1] = a[j];
j--;
}
a[j+1]=key;
}
}
void display(int *a,int n)
{
int i;
for(i=0;i<n;i++)
{
printf("%d,",a[i]);
}
}
Ans. Using C++
// cpp program for insertion sort
#include<iostream>
#include<conio.h>
using namespace std;
void insertion_sort(int *,int);
void display(int *,int);
int main()
{
int n,ele[10];
cout<<"\n\t\t\t\t\t[ INSERTION SORT ]\n";
cout<<" Enter limit >>| ";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"\tEnter element "<<i+1<<" >>| ";
cin>>ele[i];
}
cout<<"\n\n Before Sorting >>| ";
display(ele,n);
insertion_sort(ele,n);
cout<<"\n After Sorting >>| ";
display(ele,n);
getch();
return 0;
}
void insertion_sort(int *a,int n)
{
int key,j;
for(int i=1;i<n;i++)
{
key=a[i];
j=i-1;
while((a[j] > key)&&(j > -1))
{
a[j+1] = a[j];
j--;
}
a[j+1]=key;
}
}
void display(int *a,int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<",";
}
}
Try and run :
// Try and run.
Q4. Quick Sort Algorithm.
Ans. Using C
// c program for quick sort
#include <stdio.h>
#include <conio.h>
int partition (int arr[],int low,int high)
{
int temp, pivot=arr[high], i=(low - 1),j;
for (j = low; j < high; j++)
{
if (arr[j] < pivot)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return (i+1);
}
void quickSort(int arr[],int low,int high)
{
int pi;
if(low<high)
{
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void display(int arr[],int n)
{
int i;
for (i=0;i<n;i++)
printf("%d,",arr[i]);
}
int main()
{
int a[10], n=10, i;
printf("\n\t\t\t\t\t[ Quick Sort ]\n");
printf("\n Enter 10 elements >>| ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\n Before sorting : ");
display(a,n);
quickSort(a, 0, n - 1);
printf("\n After sorting : ");
display(a, n);
getch();
return 0;
}Ans. Using C++
// cpp program for quick sort
#include <iostream>
#include <conio.h>
using namespace std;
int partition (int arr[],int low,int high)
{
int temp, pivot=arr[high], i=(low - 1);
for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return (i+1);
}
void quickSort(int arr[],int low,int high)
{
if(low<high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void display(int arr[],int n)
{
for (int i=0;i<n;i++)
cout<<arr[i]<<",";
}
int main()
{
int a[10], n=10;
cout<<"\n\t\t\t\t\t[ Quick Sort ]\n";
cout<<"\n Enter 10 elements >>| ";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"\n Before sorting : ";
display(a,n);
quickSort(a, 0, n - 1);
cout<<"\n After sorting : ";
display(a, n);
getch();
return 0;
}Try and run :
// Try and run.
Q5. Merge Sort Algorithm.
Ans. Using C
// C program for Merge Sort
#include <stdio.h>
#include <conio.h>
void merge(int arr[], int const l, int const mid, int const r)
{
int const subArr1 = mid - l + 1;
int const subArr2 = r - mid;
int lArr[subArr1], rArr[subArr2];
int i,j;
int indexArr1 = 0, indexArr2 = 0;
int indexMergeArr = l;
for (i = 0; i < subArr1; i++)
lArr[i] = arr[l + i];
for (j = 0; j < subArr2; j++)
rArr[j] = arr[mid + 1 + j];
while (indexArr1 < subArr1 && indexArr2 < subArr2) {
if (lArr[indexArr1] <= rArr[indexArr2])
{
arr[indexMergeArr] = lArr[indexArr1];
indexArr1++;
}
else
{
arr[indexMergeArr] = rArr[indexArr2];
indexArr2++;
}
indexMergeArr++;
}
while (indexArr1 < subArr1)
{
arr[indexMergeArr] = lArr[indexArr1];
indexArr1++;
indexMergeArr++;
}
while (indexArr2 < subArr2)
{
arr[indexMergeArr] = rArr[indexArr2];
indexArr2++;
indexMergeArr++;
}
}
void mergeSort(int arr[], int const begin, int const end)
{
int mid;
if (begin >= end)
return;
mid = begin + (end - begin) / 2;
mergeSort(arr, begin, mid);
mergeSort(arr, mid + 1, end);
merge(arr, begin, mid, end);
}
void display(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ",a[i]);
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 }, n=6;
printf("Given array is : ");
display(arr, n);
mergeSort(arr, 0, n - 1);
printf("\nSorted array is : ");
display(arr, n);
getch();
return 0;
}
Ans. Using C++
// Cpp program for Merge Sort
#include <iostream>
#include <conio.h>
using namespace std;
void merge(int arr[], int const l, int const mid, int const r)
{
int const subArr1 = mid - l + 1;
int const subArr2 = r - mid;
auto *lArr = new int[subArr1], *rArr = new int[subArr2];
for (int i = 0; i < subArr1; i++)
lArr[i] = arr[l + i];
for (int j = 0; j < subArr2; j++)
rArr[j] = arr[mid + 1 + j];
int indexArr1 = 0, indexArr2 = 0;
int indexMergeArr = l;
while (indexArr1 < subArr1 && indexArr2 < subArr2) {
if (lArr[indexArr1] <= rArr[indexArr2])
{
arr[indexMergeArr] = lArr[indexArr1];
indexArr1++;
}
else
{
arr[indexMergeArr] = rArr[indexArr2];
indexArr2++;
}
indexMergeArr++;
}
while (indexArr1 < subArr1)
{
arr[indexMergeArr] = lArr[indexArr1];
indexArr1++;
indexMergeArr++;
}
while (indexArr2 < subArr2)
{
arr[indexMergeArr] = rArr[indexArr2];
indexArr2++;
indexMergeArr++;
}
}
void mergeSort(int arr[], int const begin, int const end)
{
if (begin >= end)
return;
int mid = begin + (end - begin) / 2;
mergeSort(arr, begin, mid);
mergeSort(arr, mid + 1, end);
merge(arr, begin, mid, end);
}
void display(int a[], int n)
{
for (int i = 0; i < n; i++)
cout << a[i] << " ";
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 }, n=6;
cout << "Given array is : ";
display(arr, n);
mergeSort(arr, 0, n - 1);
cout << "\nSorted array is : ";
display(arr, n);
getch();
return 0;
}Try and run :
// Try and run.
Q6. Heap Sort Algorithm.
Ans. Using C
// c program for heap sort
#include<stdio.h>
#include<conio.h>
void display(int a[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
void heapify(int a[],int n,int i)
{
int parent=i;
int l=2*i+1;
int r=2*i+2;
int temp;
if(l<n && a[l]>a[parent])
{
parent=l;
}
if(r<n && a[r]>a[parent])
{
parent=r;
}
if(parent != i)
{
temp=a[i];
a[i]=a[parent];
a[parent]=temp;
heapify(a,n,parent);
}
}
void heap_sort(int a[],int n)
{
int i,temp;
for(i=n/2-1;i>-1;i--)
{
heapify(a,n,i);
}
for(i=n-1;i>0;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
heapify(a,i,0);
}
}
int main()
{
int a[100]={2,10,5,6,9,3,8,4,52,50},n=10;
printf(" Before sorting : ");
display(a,n);
heap_sort(a,n);
printf("\n After sorting : ");
display(a,n);
getch();
return 0;
}Ans. Using C++
// cpp program for heap sort
#include<iostream>
#include<conio.h>
using namespace std;
void display(int a[],int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
}
void heapify(int a[],int n,int i)
{
int parent=i;
int l=2*i+1;
int r=2*i+2;
if(l<n && a[l]>a[parent])
{
parent=l;
}
if(r<n && a[r]>a[parent])
{
parent=r;
}
if(parent != i)
{
int temp=a[i];
a[i]=a[parent];
a[parent]=temp;
heapify(a,n,parent);
}
}
void heap_sort(int a[],int n)
{
for(int i=n/2-1;i>-1;i--)
{
heapify(a,n,i);
}
for(int i=n-1;i>0;i--)
{
int temp=a[0];
a[0]=a[i];
a[i]=temp;
heapify(a,i,0);
}
}
int main()
{
int a[100]={2,10,5,6,9,3,8,4,52,50},n=10;
cout<<" Before sorting : ";
display(a,n);
heap_sort(a,n);
cout<<"\n After sorting : ";
display(a,n);
getch();
return 0;
}Try and run :
For i = 2 Down To 1, a[] = 2 10 5 6 9
For i = 2:
Heapify: limit = 5, i = 2 a[] = 2 10 5 6 9
Parent = 2, left_child = 4, right_child = 5 a[] = 2 10 5 6 9
For i = 1:
Heapify: limit = 5, i = 1 a[] = 2 10 5 6 9
Parent = 1, left_child = 2, right_child = 3 a[] = 2 10 5 6 9
New: Parent = 2, Assign with left_child = 2 a[] = 2 10 5 6 9
Swap: a[i] = 2 To a[Parent] = 10, where i = 1 To Parent = 2 a[] = 2 10 5 6 9
Heapify: limit = 5 Parent = 2 a[] = 10 2 5 6 9
Parent = 2, left_child = 4, right_child = 5 a[] = 10 2 5 6 9
New: Parent = 4, Assign with left_child = 4 a[] = 10 2 5 6 9
New: Parent = 5, Assign with right_child = 5 a[] = 10 2 5 6 9
Swap: a[i] = 2 To a[Parent] = 9, where i = 2 To Parent = 5 a[] = 10 2 5 6 9
Heapify: limit = 5 Parent = 5 a[] = 10 9 5 6 2
Parent = 5, left_child = 10, right_child = 11 a[] = 10 9 5 6 2
For i = 5 Down To 2, a[] = 10 9 5 6 2
For i = 5:
Swap: a[1] = 10 To a[i] = 2 a[] = 10 9 5 6 2
Heapify: limit = 5, i = 1 a[] = 2 9 5 6 10
Parent = 1, left_child = 2, right_child = 3 a[] = 2 9 5 6 10
New: Parent = 2, Assign with left_child = 2 a[] = 2 9 5 6 10
Swap: a[i] = 2 To a[Parent] = 9, where i = 1 To Parent = 2 a[] = 2 9 5 6 10
Heapify: limit = 4 Parent = 2 a[] = 9 2 5 6 10
Parent = 2, left_child = 4, right_child = 5 a[] = 9 2 5 6 10
New: Parent = 4, Assign with left_child = 4 a[] = 9 2 5 6 10
Swap: a[i] = 2 To a[Parent] = 6, where i = 2 To Parent = 4 a[] = 9 2 5 6 10
Heapify: limit = 4 Parent = 4 a[] = 9 6 5 2 10
Parent = 4, left_child = 8, right_child = 9 a[] = 9 6 5 2 10
For i = 4:
Swap: a[1] = 9 To a[i] = 2 a[] = 9 6 5 2 10
Heapify: limit = 4, i = 1 a[] = 2 6 5 9 10
Parent = 1, left_child = 2, right_child = 3 a[] = 2 6 5 9 10
New: Parent = 2, Assign with left_child = 2 a[] = 2 6 5 9 10
Swap: a[i] = 2 To a[Parent] = 6, where i = 1 To Parent = 2 a[] = 2 6 5 9 10
Heapify: limit = 3 Parent = 2 a[] = 6 2 5 9 10
Parent = 2, left_child = 4, right_child = 5 a[] = 6 2 5 9 10
For i = 3:
Swap: a[1] = 6 To a[i] = 5 a[] = 6 2 5 9 10
Heapify: limit = 3, i = 1 a[] = 5 2 6 9 10
Parent = 1, left_child = 2, right_child = 3 a[] = 5 2 6 9 10
For i = 2:
Swap: a[1] = 5 To a[i] = 2 a[] = 5 2 6 9 10
Heapify: limit = 2, i = 1 a[] = 2 5 6 9 10
Parent = 1, left_child = 2, right_child = 3 a[] = 2 5 6 9 10
0 Comments
If you have any doubt. Let me know.