Lab: - 01
Write a program to sort an array by BUBBLE SORT technique.
/* Bubble sort code */
#include <stdio.h>
int main()
{
int array[100], n, c, d, swap;
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 = 0 ; c < n - 1; c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1]) /* For decreasing order use '<' instead of '>' */
{
swap= array[d];
array[d]= array[d+1];
array[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}
[1]
The Output is: -
[2]
Lab: - 02
Write a program to sort an array by INSERTION SORT technique.
#include<stdio.h>
int main(){
/* Here i & j for loop counters, temp for swapping,
* count for total number of elements, number[] to
* store the input numbers in array. You can increase
* or decrease the size of number array as per requirement
*/
int i, j, count, temp, number[25];
printf("How many numbers u are going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
// This loop would store the input numbers in array
for(i=0;i<count;i++)
scanf("%d",&number[i]);
// Implementation of insertion sort algorithm for(i=1;i<count;i+
+)
{
temp=number[i]; j=i-1;
while((temp<number[j])&&(j>=0))
{
number[j+1]=number[j];
j=j-1;
}
number[j+1]=temp;
}
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
}
[3]
The Output is: -
[4]
Lab: - 03
Write a program to sort an array by SELECTION SORT technique.
#include <stdio.h>
int main()
{
int array[100], n, c, d, position, 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 = 0; c < (n - 1); c++) // finding minimum element (n-1) times
{
position = c;
for (d = c + 1; d < n; d++)
{
if (array[position] > array[d])
position = d;
}
if (position != c)
{
t = array[c];
array[c] = array[position];
array[position] = t;
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}
[5]
The Output is: -
[6]
Lab: - 04
Write a program to sort an array by QUICK SORT technique.
#include<stdio.h>
void quicksort(int number[25],int first,int last)
{
int i, j, pivot, temp;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j)
{
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
[7]
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
}
The Output is: -
[8]
Lab: - 05
Write a program to sort an array by MERGE SORT technique.
#include<stdio.h>
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
int main()
{
int a[30],n,i;
printf("Enter no of elements:");
scanf("%d",&n);
printf("Enter array elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("\nSorted array is :");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
void mergesort(int a[],int i,int j)
{
int mid;
if(i<j)
{
mid=(i+j)/2;
mergesort(a,i,mid); //left recursion
mergesort(a,mid+1,j); //right recursion
merge(a,i,mid,mid+1,j); //merging of two sorted sub-array
}
}
[9]
void merge(int a[],int i1,int j1,int i2,int j2)
{
int temp[50]; //array used for merging
int i,j,k;
i=i1; //beginning of the first list
j=i2; //beginning of the second list
k=0;
while(i<=j1 && j<=j2) //while elements in both lists
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=j1) //copy remaining elements of the first list temp[k++]=a[i+
+];
while(j<=j2) //copy remaining elements of the second list temp[k+
+]=a[j++];
//Transfer elements from temp[] back to a[]
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}
The Output is: -
[10]
Lab: - 06
Write a program to sort an array by HEAP SORT technique.
#include <stdio.h>
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i)
{
int left, right, largest;
largest = i;
left = 2 * i + 1;
right = 2 * i + 2;
// Check if left child exists and is larger than its parent
if (left < n && arr[left] > arr[largest]) largest = left;
// Check if right child exists and larger than its parent
if (right < n && arr[right] > arr[largest]) largest = right;
// if root is not the largest
if (largest != i) {
swap(&arr[i], &arr[largest]); //make root the largest
heapify(arr, n, largest); // Apply heapify to the largest node
}
}
void heap_sort(int arr[], int n)
{
int i;
for (i = (n / 2) - 1; i >= 0; i--)
heapify(arr, n, i);
for (i = n - 1; i >= 0; i--)
{
swap(&arr[0], &arr[i]); //Move the largest element at root to
the end
[11]
heapify(arr, i, 0); //Apply heapify to reduced heap
}
}
int main()
{
int arr[] = { 20, 13, 34, 56, 12, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
heap_sort(arr, n);
printf("\nAfter performing Heap Sort:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
The Output is: -
Array:
20 13 34 56 12 10
After performing Heap Sort:
10 12 13 20 34 56
[12]
Lab: - 07
Write a program to sort an array by SHELL SORT technique.
#include<stdio.h>
void sort(int a[],int n)
{
int gap,i,j,temp;
for(gap=n/2;gap>0;gap/=2)
{
for(i=gap;i<n;i+=1)
{
temp=a[i];
for(j=i;j>=gap&&a[j-gap]>temp;j-=gap)
a[j]=a[j-gap];
a[j]=temp;
}
}
}
int main()
{
int a[20],i,n;
printf("Enter number of elements:");
scanf("%d",&n);
printf("Enter array elements:\n"); for(i=0;i<n;
++i)
scanf("%d",&a[i]);
sort(a,n);
printf("\nArray after shell sort:\n");
for(i=0;i<n;++i)
printf("%d ",a[i]);
return 0;
}
[13]
The Output is: -
Enter number of elements: 5 Enter
array elements:
56 7 2 9 12
Array after shell sort: 2 7 9
12 56
[14]
Lab: - 08
Write a program to sort an array by BUCKET SORT technique.
#include <stdio.h>
#include <stdlib.h>
struct bucket
{
int count;
int* value;
};
int compareIntegers(const void* first, const void* second)
{
int x = *((int*)first), y =*((int*)second);
if (x == y)
{
return 0;
}
else if (x < y)
{
return -1;
}
else
{
return 0;
}
}
void bucketSort(int array[],int n)
{
struct bucket buckets[3];
int i, j, k;
for (i = 0; i < 3; i++)
{
buckets[i].count = 0;
buckets[i].value = (int*)malloc(sizeof(int) * n);
}
for (i = 0; i < n; i++)
[15]
{
if (array[i] < 0)
{
buckets[0].value[buckets[0].count++] = array[i];
}
else if (array[i] > 10)
{
buckets[2].value[buckets[2].count++] = array[i];
}
else
{
buckets[1].value[buckets[1].count++] = array[i];
}
}
for (k = 0, i = 0; i < 3; i++)
{
// now using quicksort to sort the elements of buckets
qsort(buckets[i].value, buckets[i].count, sizeof(int), &compareIntegers);
for (j = 0; j < buckets[i].count; j++)
{
array[k + j] = buckets[i].value[j];
}
k += buckets[i].count;
free(buckets[i].value);
}
}
int main(char *arg[])
{
int array[100] = { 5, -34, 10, 1, -42, 123, 2, 395, 5, 4, 1234, 7};
int i = 12,j,k,n;
n=i;
printf("Before Sorting\n");
for (j = 0; j<i; j++)
{
printf("%d ", array[j]);
}
bucketSort(array, n);
[16]
printf("\n After Sorting\n");
for (k = 0; k<i; k++)
printf("%d ", array[k]);
return 0;
}
The Output is:-
Before Sorting 39 5
12 64 35 46
After Sorting
5 12 35 39 46 64
[17]
Lab: - 09
Write a program to sort an array by COUNTING SORT technique.
#include<stdio.h>
void counting_sort(int a[],int n,int max)
{
int count[50]={0},i,j;
for(i=0;i<n;++i)
count[a[i]]=count[a[i]]+1;
printf("\nSorted elements are:");
for(i=0;i<=max;++i)
for(j=1;j<=count[i];++j)
printf("%d ",i);
}
int main()
{
int a[50],n,i,max=0;
printf("Enter number of elements:");
scanf("%d",&n);
printf("\nEnter elements:");
for(i=0;i<n;++i)
{
scanf("%d",&a[i]);
if(a[i]>max)
max=a[i];
}
counting_sort(a,n,max);
return 0;
}
[18]
The Output is: -
[19]
Lab: - 10
Write a program to sort an array by RADIX SORT technique.
#include<stdio.h>
// Function to find largest element
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;
// Function to perform sorting void
RadixSort(int a[], int n)
int bucket[10][10], bucket_count[10];
int i, j, k, remainder, NOP=0, divisor=1, large, pass;
[20]
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++)
{
[21]
a[i] = bucket[k][j];
i++;
divisor *= 10;
for(i = 0; i < n; i++)
printf("%d",a[i]);
printf("\n");
//program starts here
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 :: ");
[22]
for(i = 0; i < n; i++)
printf("%d ",a[i]); printf("\
n");
return 0;
The Output is: -
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
[23]
Lab: - 11
Write a program to search an Element from array by Linear Search.
#include <stdio.h>
int main()
{
int array[100], search, c, n;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integer(s)\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter a number to search\n");
scanf("%d", &search);
for (c = 0; c < n; c++)
{
if (array[c] == search) /* If required element is found */
{
printf("%d is present at location %d.\n", search, c+1);
break;
}
}
if (c == n)
printf("%d isn't present in the array.\n", search);
return 0;
}
[24]
The Output is: -
[25]
Lab: - 12
Write a program to search an Element from array by Binary Search.
#include <stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
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]);
printf("Enter value to find\n");
scanf("%d", &search);
first = 0;
last = - 1;
middle = (first+last)/2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search)
{
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
printf("Not found! %d isn't present in the list.\n", search);
return 0;
}
[26]
The Output is: -
[27]