Ex no : 3.
1a
IMPLEMENT BUBBLE SORT
Date:
Aim:
To Write a program to complete bubble() function which is used to implement Bubble Sort.
Pseudocode:
BEGIN
procedure bubbleSort(arr: array of integers)
n = length(arr)
for i from 0 to n-1
for j from 0 to n-i-1
if arr[j] > arr[j+1]
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
print("%d ", arr[i]);
END
Source Code:
#include <stdio.h>
void bubble(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n-1; i++) {
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main() {
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
bubble(arr, n);
printf("Sorted array:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
717822D114
OUTPUT:
Result:
Thus the c program has been executed successfully and the output has been verified.
717822D114
Ex no : 3.1b
IMPLEMENT INSERTION SORT
Date:
Aim:
To Write a program to complete the insert() function which is used to implement Insertion Sort.
Pseudocode:
BEGIN
procedure insertionSort(arr: array of integers)
n = length(arr)
for i from 1 to n-1
key = arr[i]
j=i-1
while j >= 0 and arr[j] > key
arr[j + 1] = arr[j]
j=j-1
end while
arr[j + 1] = key
printf("%d ", arr[i]);
END
Source Code:
#include <stdio.h>
void insert(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
insert(arr, n);
printf("Sorted array:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;}
717822D114
OUTPUT:
Result:
Thus the c program has been executed successfully and the output has been verified.
717822D114
Ex no : 3.2a
IMPLEMENT MERGE SORT
Date:
Aim:
To Write a program for implementing the sort which is used in the following diagram.
Pseudocode:
BEGIN
function merge(arr, left, mid, right)
i = left,j = mid + 1,k = 0
n1 = mid - left + 1,n2 = right - mid
temp = array of size n1 + n2
while i < n1 and j < n2
if arr[i] <= arr[j]
temp[k] = arr[i]
i=i+1
else
temp[k] = arr[j]
j=j+1
k=k+1
while i < n1
temp[k] = arr[i]
i=i+1
k=k+1
temp[k] = arr[j]
j=j+1
k=k+1
for i = left to right
arr[i] = temp[i - left]
function merge_sort(arr, left, right)
if left < right
mid = (left + right) / 2
merge_sort(arr, left, mid)
merge_sort(arr, mid + 1, right)
merge(arr, left, mid, right)
END
Source Code:
717822D114
#include<stdlib.h>
#include<stdio.h>
void merge(int a[], int low, int mid, int high)
{
int i,k,m,l,temp[50];
l=low;
i=low;
m=mid+1;
while((l<=mid)&&(m<=high))
{
if(a[l]<=a[m])
temp[i++]=a[l++];
else //a[l]>a[m]
temp[i++]=a[m++];
}
while(l<=mid)
temp[i++]=a[l++];
while(m<=high)
temp[i++]=a[m++];
for(k=low;k<=high;k++)
a[k]=temp[k];
}
void partition(int arr[], int low, int high)
{
if (low < high)
{
int mid = (low+high)/2;
partition(arr, low, mid);
partition(arr, mid+1, high);
merge(arr, low, mid, high);
}
}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
void main()
{
int i,arr[20],n;
printf("Enter the size of array: ");
scanf("%d",&n);
printf("Enter the array elements: ");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("Given array is \n");
printArray(arr, n);
partition(arr, 0, n-1);
printf("\nSorted array is \n");
printArray(arr, n);
}
717822D114
OUTPUT:
Result:
Thus the c program has been executed successfully and the output has been verified
717822D114
Ex no : 3.2b
IMPLEMENT QUICK SORT
Date:
Aim:
To Write a program for implementing the sort which is used in the following diagram.
Pseudocode:
BEGIN
procedure quicksort(arr:array of integers,low:integer,high:integer)
if low < high then
pivotIndex = partition(arr, low, high)
quicksort(arr, low, pivotIndex - 1)
quicksort(arr, pivotIndex + 1, high)
procedure partition(arr:array of integers, low:integer,high:integer)returns integer
pivot = arr[low]
left = low + 1
right = high
while left <= right do
while left <= high and arr[left] <= pivot do
left = left + 1
end while
while right > low and arr[right] > pivot do
right = right - 1
end while
if left < right then
swap(arr, left, right)
end if
end while
swap(arr, low, right)
return right
procedure swap(arr: array of integers, i: integer, j: integer)
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
END
717822D114
Source Code:
#include <stdlib.h>
#include <stdio.h>
void quicksort(int arr[25],int low,int high){
int i, j, pivot, temp, val;
if(low<high){
pivot=low;
//printf("Pivot = %d\n",pivot);
i=low;
j=high;
while(i<j){
while(arr[i]<=arr[pivot]&&i<high)
i++;
while(arr[j]>arr[pivot]&&j>low)
j--;
if(i<j){
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}//while
temp=arr[pivot];
arr[pivot]=arr[j];
arr[j]=temp;
quicksort(arr,low,j-1);
quicksort(arr,j+1,high);
}//if
}
int main(){
int i, count, arr[25];
printf("Number of elements in the array: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&arr[i]);
quicksort(arr,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",arr[i]);
return 0;
}
717822D114
OUTPUT:
Result:
Thus the c program has been executed successfully and the output has been verified.
717822D114
Ex no : 3.3a
LINEAR SEARCH
Date:
Aim:
Given an array arr[] of n elements, write a program to search a given element x in arr[].
Pseudocode:
BEGIN
procedure linearSearch(arr:array of integers,n:integer,x:integer) returns integer
for i from 0 to n-1
if arr[i] is equal to x
return i
end for
return -1
procedure main()
arr: array[100] of integer
size, i, key, result: integer
print("Enter the size of array: ")
read size
print("Enter the array elements: ")
for i from 0 to size-1
read arr[i]
print("Enter the key to search: ")
read key
result = linearSearch(arr, size, key)
if result is equal to -1
print("Element is not present in array")
else
print("Element is present at index ", result)
END
Source Code:
#include <stdio.h>
int linearSearch(int arr[], int n, int x)
{
int i;
for(i=0;i<n;i++)
if (arr[i] == x)
return i;
return -1;
}
void main()
{
int arr[100],size,i,key;
printf("Enter the size of array: ");
scanf("%d",&size);
printf("Enter the array elements: ");
for(i=0;i<size;i++)
scanf("%d",&arr[i]);
printf("Enter the key to search: ");
scanf("%d",&key);
int result = linearSearch(arr, size, key);
717822D114
(result == -1)?
printf("Element is not present in array"):
printf("Element is present at index %d", result);
}
OUTPUT:
Result:
Thus the c program has been executed successfully and the output has been verified.
717822D114
Ex no : 3.3b
BINARY SEARCH
Date:
Aim:
Given a sorted array arr[] of n elements, write a program to search a given element x in arr[] using binary search.
Pseudocode:
BEGIN
procedure binarySearch(arr:array of integers,l:integer,h:integer,x:integer) returns integer
if l <= h then
mid = (l + h) / 2
if arr[mid] is equal to x then
return mid
else if arr[mid] > x then
return binarySearch(arr, l, mid - 1, x)
else
return binarySearch(arr, mid + 1, h, x)
end if
end if
return -1
procedure main()
arr: array[10] of integer
n, i, x, result: integer
print("Size: ")
read n
print("Elements: ")
for i from 0 to n-1
read arr[i]
print("Search Key: ")
read x
result = binarySearch(arr, 0, n-1, x)
if result is equal to -1 then
print("Element is not present in array")
else
print("Element is present at index ", result)
END
Source Code:
#include <stdio.h>
int binarySearch(int arr[], int l, int h, int x)
{
if (l<=h)
{
int mid = (l+h)/2;
if (arr[mid] == x)
return mid;
else if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
else
return binarySearch(arr, mid+1, h, x);
}
return -1;
}
void main()
717822D114
{
int arr[10],n,i,x;
printf("Size:");
scanf("%d",&n);
printf("Elements:");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("Search Key:");
scanf("%d",&x);
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array"):
printf("Element is present at index %d", result);
}
OUTPUT:
717822D114
Result:
Thus the c program has been executed successfully and the output has been verified.
Ex no : 3.4a
717822D114
Date:
LINEAR PROBING
Aim:
To Write a program to insert the given keys into the hash table using linear probing.
Pseudocode:
BEGIN
procedure LinearProbing(arr: array of integers, n: integer, table_size: integer)
for i from 0 to table_size - 1
arr[i] = -1
for i from 0 to n - 1
print("Enter [", i+1, "] element: ")
read element
j=0
while true
HashKey = ((element % table_size) + j) % table_size
if arr[HashKey] is equal to -1
arr[HashKey] = element
break
else
j=j+1
print("Hash Table:")
print("Index Value")
for i from 0 to table_size - 1
print(i, " ", arr[i])
procedure main()
table_size, n: integer
arr: array of integers
print("Enter the table size: ")
read table_size
print("Enter the number of elements: ")
read n
LinearProbing(arr, n, table_size)
END
Source Code:
#include<stdio.h>
void LinearProbing(int arr[],int n,int table_size)
{
int i,element,j,HashKey;
for(i=0;i<n;i++)
{
printf("Enter [%d] element: ",i+1);
scanf("%d",&element);
j=0;
while(1)
{
HashKey=((element % table_size) + j ) % table_size;
if(arr[HashKey]==-1)
{
arr[HashKey]=element;
break;
}
else
j++;
717822D114
}
}
printf("Hash Table:\n");
printf("Index Value\n");
for(i=0;i<table_size;i++)
printf("%d %d\n",i,arr[i]);
}
void main()
{
int table_size,i,n;int arr[10];
printf("Enter the table size: ");
scanf("%d",&table_size);
printf("Enter the number of elements: ");
scanf("%d",&n);
for(i=0;i<table_size;i++)
arr[i]=-1;
LinearProbing(arr,n,table_size);
}
OUTPUT:
717822D114
Result:
Thus the c program has been executed successfully and the output has been verified.
Ex no : 3.4b
QUADRATIC PROBING
717822D114
Aim:
To Write a program to insert the given keys into the hash table using quadratic probing.
Pseudocode:
BEGIN
procedure QuadraticProbing(arr: array of integers, n: integer, table_size: integer)
for i from 0 to table_size - 1
arr[i] = -1
for i from 0 to n - 1
print("Enter [", i, "] element: ")
read element
j=0
while true
HashKey = ((element % table_size) + (j * j)) % table_size
if arr[HashKey] is equal to -1
arr[HashKey] = element
break
else
j=j+1
print("Index:", HashKey, ", Value:", arr[HashKey])
print("Hash Table:")
print("Index Value")
for i from 0 to table_size - 1
print(i, " ", arr[i]
procedure main()
table_size, n: integer
arr: array of integers
print("Enter the table size: ")
read table_size
print("Enter the number of elements: ")
read n
QuadraticProbing(arr, n, table_size)
END
Source Code:
#include<stdio.h>
void QuadraticProbing(int arr[],int n,int table_size)
{
int i,element,j,HashKey;
for(i=0;i<n;i++)
{
printf("Enter [%d] element: ",i);
scanf("%d",&element);
j=0;
while(1)
{
HashKey=((element % table_size) + (j*j) ) % table_size;
if(arr[HashKey]==-1)
{
arr[HashKey]=element;
break;
}
else
j++;
}
717822D114
printf("Index:%d, Value:%d\n",HashKey,arr[HashKey]);
}
printf("Hash Table:\n") ;
printf("Index Value\n");
for(i=0;i<table_size;i++)
printf("%d %d\n",i,arr[i]);
}
void main()
{
int table_size,i,n;int arr[10];
printf("Enter the table size: ");
scanf("%d",&table_size);
printf("Enter the number of elements: ");
scanf("%d",&n);
for(i=0;i<table_size;i++)
arr[i]=-1;
QuadraticProbing(arr,n,table_size);
}
OUTPUT:
717822D114
Result:
Thus the c program has been executed successfully and the output has been verified.
Ex no : 3.4c
717822D114
Date:
DOUBLE HASHING
Aim:
To Write a program to insert the given keys into the hash table using double hashing.
Pseudocode:
BEGIN
procedure DoubleProbing(arr: array of integers, n: integer, table_size: integer)
R, flag, t, i, element, j, HashKey: integer
for R from table_size - 1 downto 2
flag = 0
for t from 2 to R - 1
if R % t is equal to 0
flag = 1
break
end if
end for
if flag is equal to 0
break
print("Largest Prime Number =", R)
for i from 0 to n - 1
print("Enter [", i, "] element: ")
read element
j=0
while true
HashKey = ((element % table_size) + (j * (R - (element % R)))) % table_size
if arr[HashKey] is equal to -1
arr[HashKey] = element
break
else
j=j+1
print("Hash Table:")
print("Index Value")
for i from 0 to table_size - 1
print(i, " ", arr[i])
procedure main()
table_size, n: integer
arr: array of integers
print("Enter the table size: ")
read table_size
print("Enter the number of elements: ")
read n
for i from 0 to table_size - 1
arr[i] = -1
DoubleProbing(arr, n, table_size)
END
Source Code:
#include<stdio.h>
void DoubleProbing(int arr[],int n,int table_size)
{
int i,element,j,HashKey,R,flag,t;
for(R=table_size-1;R>1;R--)
{
flag=0;
717822D114
for(t=2;t<R;t++)
{
if(R%t ==0)
{
flag=1;
break;
}
}
if(flag==0)
break;
}
printf("Largest Prime Number = %d\n",R);
for(i=0;i<n;i++)
{
printf("Enter [%d] element: ",i);
scanf("%d",&element);
j=0;
while(1)
{
HashKey=((element % table_size) + (j*(R-(element % R))) ) % table_size;
if(arr[HashKey]==-1)
{
arr[HashKey]=element;
break;
}
else
j++;
}
}
printf("Hash Table:\n") ;
printf("Index Value\n");
for(i=0;i<table_size;i++)
printf("%d %d\n",i,arr[i]);
}
void main()
{
int table_size,i,n;int arr[10];
printf("Enter the table size: ");
scanf("%d",&table_size);
printf("Enter the number of elements: ");
scanf("%d",&n);
for(i=0;i<table_size;i++)
arr[i]=-1;
DoubleProbing(arr,n,table_size);
}
OUTPUT:
717822D114
Result:
Thus the c program has been executed successfully and the output has been verified.
717822D114
717822D114
