SORTING(Bubble Sort)
Aim of the experiment: Write a C program that implement Bubble Sort method to sort a given
list of integers in descending order.
Programming code
#include<stdio.h>
#include<conio.h>
#define MAX 20
void main()
{
int arr[MAX],i,j,k,temp,n,xchanges;
clrscr();
printf("Enter the number of elements : ");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Unsorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
for (i = 0; i < n-1 ; i++)
{
xchanges=0;
for (j = 0; j <n-1-i; j++)
{
if (arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
xchanges++;
if(xchanges==0) /*If list is sorted*/
break;
printf("After Pass %d elements are : ",i+1);
for (k = 0; k < n; k++)
printf("%d ", arr[k]);
printf("\n");
}
printf("Sorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
Output
Enter the number of elements : 5
Enter element 1 : 10
Enter element 2 : 2
Enter element 3 : 30
Enter element 4 : 5
Enter element 5 : 6
Unsorted list is :
10 2 30 5 6
After Pass 1 elements are : 2 10 5 6 30
After Pass 2 elements are : 2 5 6 10 30
Sorted list is :
2 5 6 10 30
Conclusion: The program has been executed successfully and produce the correct output.
Quick Sort
Aim of the experiment: Write a C program that implement Quick Sort method to sort a given
list of integers in ascending order:
Programming code
#include<stdio.h>
#include<conio.h>
#define MAX 30
enum bool { FALSE,TRUE };
void quick(int arr[],int low,int up);
void display(int arr[],int low,int up);
void main()
{
int array[MAX],n,i;
clrscr();
printf("Enter the number of elements : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&array[i]);
}
printf("Unsorted list is :\n");
display(array,0,n-1);
printf("\n");
quick(array,0,n-1);
printf("Sorted list is :\n");
display(array,0,n-1);
printf("\n");
}void quick(int arr[],int low,int up)
{
int piv,temp,left,right;
enum bool pivot_placed=FALSE;
left=low;
right=up;
piv=low;
if(low>=up)
return;
printf("Sublist : ");
display(arr,low,up);
while(pivot_placed==FALSE)
{
while( arr[piv]<=arr[right] && piv!=right )
right=right-1;
if( piv==right )
pivot_placed=TRUE;
if( arr[piv] > arr[right] )
{
temp=arr[piv];
arr[piv]=arr[right];
arr[right]=temp;
piv=right;
}
while( arr[piv]>=arr[left] && left!=piv )
left=left+1;
if(piv==left)
pivot_placed=TRUE;
if( arr[piv] < arr[left] )
{
temp=arr[piv];
arr[piv]=arr[left];
arr[left]=temp;
piv=left;
}
}
printf("-> Pivot Placed is %d -> ",arr[piv]);
display(arr,low,up);
printf("\n");
quick(arr,low,piv-1);
quick(arr,piv+1,up);
}
void display(int arr[],int low,int up)
{
int i;
for(i=low;i<=up;i++)
printf("%d",arr[i]);
}
Output
Enter the number of elements : 7
Enter element 1 : 10
Enter element 2 : 2
Enter element 3 : 36
Enter element 4 : 5
Enter element 5 : 64
Enter element 6 : 58
Enter element 7 : 21
Unsorted list is :
10 2 36 5 64 58 21
Sublist : 10 2 36 5 64 58 21 -> Pivot Placed is 10 -> 5 2 10 36 64 58 21
Sublist : 5 2 -> Pivot Placed is 5 -> 2 5
Sublist : 36 64 58 21 -> Pivot Placed is 36 -> 21 36 58 64
Sublist : 58 64 -> Pivot Placed is 58 -> 58 64
Sorted list is :
2 5 10 21 36 58 64
Conclusion: The program has been executed successfully and produce the correct output.
Selection Sort
Aim of the experiment: Write a C program that implement selection Sort method to sort a
given list of integers in ascending order:
Programming code
#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],n,i,j,min,temp;
clrscr();
printf("\n Enter the Number of Elements: ");
scanf("%d",&n);
printf("\n Enter %d Elements: ",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(a[min]>a[j])
min=j;
}
if(min!=i)
{
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
printf("\n The Sorted array in ascending order: ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
getch();
}
Output:
Enter the no of elements: 5
Enter 5 elements: 4 1 9 3 6
The sorted array in ascending order: 1 3 4 6 9
Insertion Sort
Aim of the experiment: Write a C program that implement insertion Sort method to sort a
given list of integers in ascending order:
Programming code
#include <stdio.h>
int main()
{
int n, array[1000], c, d, t;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 1 ; c <= n - 1; c++) {
d = c;
while ( d > 0 && array[d-1] > array[d]) {
t = array[d];
array[d] = array[d-1];
array[d-1] = t;
d- -;
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c <= n - 1; c++) {
printf("%d\n", array[c]);
}
return 0;
}
Output:
Enter the no of elements:5
Enter 5 integers:4 3 -1 2 1
Sorted list in ascending order: -1 1 2 3 4
Radix Sort
Aim of the experiment: Write a C program that implement radix Sort method to sort a given
list of integers in ascending order:
Programming code
#include<stdio.h>
int largest(int a[], int n)
{
int large = a[0], i;
for(i = 1; i < n; i++)
{
if(large < a[i])
large = a[i];
}
return large;
}
void RadixSort(int a[], int n)
{
int bucket[10][10], bucket_count[10];
int i, j, k, remainder, NOP=0, divisor=1, large, pass;
large = largest(a, n);
printf("The large element %d\n",large);
while(large > 0)
{
NOP++;
large/=10;
}
for(pass = 0; pass < NOP; pass++)
{
for(i = 0; i < 10; i++)
{
bucket_count[i] = 0;
}
for(i = 0; i < n; i++)
{
remainder = (a[i] / divisor) % 10;
bucket[remainder][bucket_count[remainder]] = a[i];
bucket_count[remainder] += 1;
}
i = 0;
for(k = 0; k < 10; k++)
{
for(j = 0; j < bucket_count[k]; j++)
{
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;
for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
}
}
int main()
{
int i, n, a[10];
printf("Enter the number of elements :: ");
scanf("%d",&n);
printf("Enter the elements :: ");
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
RadixSort(a,n);
printf("The sorted elements are :: ");
for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
OUTPUT:
Enter the number of elements :: 7
Enter the elements :: 21 32 11 58 98 45 21
The large element 98
21 11 21 32 45 58 98
11 21 21 32 45 58 98
The sorted elements are :: 11 21 21 32 45 58 98
Heap Sort
Aim of the experiment: Write a C program that implement heap Sort method to sort a given list
of integers in ascending order:
Programming code
#include<stdio.h>
void create(int []);
void down_adjust(int [],int);
void main()
{
int heap[30],n,i,last,temp;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("\nEnter elements:");
for(i=1;i<=n;i++)
scanf("%d",&heap[i]);
heap[0]=n;
create(heap);
while(heap[0] > 1)
{
swap heap[1] and heap[last]
last=heap[0];
temp=heap[1];
heap[1]=heap[last];
heap[last]=temp;
heap[0]--;
down_adjust(heap,1);
}
printf("\nArray after sorting:\n");
for(i=1;i<=n;i++)
printf("%d ",heap[i]);
}
void create(int heap[])
{
int i,n;
n=heap[0];
for(i=n/2;i>=1;i--)
down_adjust(heap,i);
}
void down_adjust(int heap[],int i)
{
int j,temp,n,flag=1;
n=heap[0];
while(2*i<=n && flag==1)
{
j=2*i;
if(j+1<=n && heap[j+1] > heap[j])
j=j+1;
if(heap[i] > heap[j])
flag=0;
else
{
temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
i=j;
}
}
}
Output
Enter no. of elements: 5
Enter elements: 12 8 46 23 7
Array after sorting:
7 8 12 23 46
2way merge Sort
Aim of the experiment: Write a C program that implement 2way merge Sort method to sort a
given list of integers in ascending order:
Programming code
#include<stdlib.h>
#include<stdio.h>
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2; //Same as (l+r)/2 but avoids overflow for large l & h
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
Output:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
