1

AIM: Write an algorithm and program to implement BINARY SEARCH.

ALGORITHM :-

Step 1: Declare the variables and input all elements of an array in sorted order (ascending or
descending).

Step 2: Divide the lists of array elements into halves.

Step 3: Now compare the target elements with the middle element of the array. And if the
value of the target element is matched with the middle element, return the middle element's
position and end the search process.

Step 4: If the target element is less than the middle element, we search the elements into the
lower half of an array.

Step 5: If the target element is larger than the middle element, we need to search the element
into the greater half of the array.

Step 6: We will continuously repeat steps 4, 5, and 6 till the specified element is not found in
the sorted array.

PROGRAM :-
#include <iostream>
#include <conio.h>
using namespace std;
int main ()
{
// declaration of the variables and array
int arr[100], st, mid, end, i, num, tgt;

cout << " Define the size of the array: " << endl;
cin >> num; // get size

// enter only sorted array

cout << " Enter the values in sorted array either ascending or descending order: " <<
endl;
// use for loop to iterate values
for (i = 0; i < num; i++)
{
cout << " arr [" << i << "] = ";
cin >> arr[i];

EN21CS301878, YAMAN KUMAR SAHOO

 2

}
// initialize the starting and ending variable's values
st = 0;
end = num - 1; // size of array (num) - 1
// define the item or value to be search
cout << " Define a value to be searched from sorted array: " << endl;
cin >> tgt;

// use while loop to check 'st', should be less than equal to 'end'.
while ( st <= end)
{
// get middle value by splitting into half
mid = ( st + end ) / 2;
/* if we get the target value at mid index, print the position and exit from the program.
*/
if (arr[mid] == tgt)
{
cout << " Element is found at index " << (mid + 1);
exit (0); // use for exit program the program
}
// check the value of target element is greater than the mid element' value
else if ( tgt > arr[mid])
{
st = mid + 1; // set the new value for st variable
}

// check the value of target element is less than the mid element' value
else if ( tgt < arr[mid])
{
end = mid - 1; // set the new value for end variable
}
}
cout << " Number is not found. " << endl;
return 0;
}

OUTPUT:-
Define the size of the array:
10
Enter the values in sorted array either ascending or descending order:
Arr [0] = 12 Arr [1] = 24 Arr [2] = 36
Arr [3] = 48 Arr [4] = 50 Arr [5] = 54
Arr [6] = 58 Arr [7] = 60 Arr [8] = 72
Arr [9] = 84
Define a value to be searched from sorted array:
50
Element is found at index 5

EN21CS301878, YAMAN KUMAR SAHOO

 3

AIM: Write an algorithm and program to implement LINEAR SEARCH.

ALGORITHM :-

Step 1: Read the item to be searched by the user.

Step 2: Compare the search element with the first element in the list.

Step 3: If they both matches, terminate the function.

Step 4: Else compare the search element with the next element in the list.

Step 5: Repeat steps 3 and 4 until the element to be search is found.

PROGRAM :-
// Linear Search in C++

#include <iostream>
using namespace std;

int search(int array[], int n, int x) {

// Going through array sequencially

for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}

int main() {
int array[] = {2, 4, 0, 1, 9};
int x = 1;
int n = sizeof(array) / sizeof(array[0]);

int result = search(array, n, x);

(result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result;
}

OUTPUT:-
Element found at index: 1

EN21CS301878, YAMAN KUMAR SAHOO

 4

AIM: Write an algorithm and program to implement INSERTION SORT.

ALGORITHM :-

Step 1 - If the element is the first element, assume that it is already sorted. Return 1.

Step2 - Pick the next element, and store it separately in a key.

Step3 - Now, compare the key with all elements in the sorted array.

Step 4 - If the element in the sorted array is smaller than the current element, then move
to the next element. Else, shift greater elements in the array towards the right.

Step 5 - Insert the value.

Step 6 - Repeat until the array is sorted.

PROGRAM :-

// C++ program for insertion sort

#include <bits/stdc++.h>
using namespace std;

// Function to sort an array using

// insertion sort
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// Move elements of arr[0..i-1],
// that are greater than key,
// to one position ahead of their
// current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
EN21CS301878, YAMAN KUMAR SAHOO
 5

arr[j + 1] = key;
}
}

void printArray(int arr[], int n)

{
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, N);
printArray(arr, N);

return 0;
}

OUTPUT:-

5 6 11 12 13

EN21CS301878, YAMAN KUMAR SAHOO

 6

AIM: Write an algorithm and program to implement BUBBLE SORT.

ALGORITHM :-

1. begin BubbleSort(arr)
2. for all array elements
3. if arr[i] > arr[i+1]
4. swap(arr[i], arr[i+1])
5. end if
6. end for
7. return arr
8. end BubbleSort

PROGRAM :-

#include <bits/stdc++.h>
using namespace std;
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}

// If no two elements were swapped

// by inner loop, then break
if (swapped == false)
break;
}
}
// Function to print an array
void printArray(int arr[], int size)

EN21CS301878, YAMAN KUMAR SAHOO

 7

{
int i;
for (i = 0; i < size; i++)
cout << " " << arr[i];
}
int main()
{
int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
int N = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, N);
cout << "Sorted array: \n";
printArray(arr, N);
return 0;
}

OUTPUT:-

Sorted array:
11 12 22 25 34 64 90

EN21CS301878, YAMAN KUMAR SAHOO

 8

AIM: Write an algorithm and program to implement SELECTION SORT.

ALGORITHM :-

1. SELECTION SORT(arr, n)
2. Step 1: Repeat Steps 2 and 3 for i = 0 to n-1
3. Step 2: CALL SMALLEST(arr, i, n, pos)
4. Step 3: SWAP arr[i] with arr[pos]
5. [END OF LOOP]
6. Step 4: EXIT
7. SMALLEST (arr, i, n, pos)
8. Step 1: [INITIALIZE] SET SMALL = arr[i]
9. Step 2: [INITIALIZE] SET pos = i
10. Step 3: Repeat for j = i+1 to n
11. if (SMALL > arr[j])
12. SET SMALL = arr[j]
13. SET pos = j
14. [END OF if]
15. [END OF LOOP]
16. Step 4: RETURN pos

PROGRAM :-
// C++ program for implementation of
// selection sort
#include <bits/stdc++.h>
using namespace std;

// Function for Selection sort

void selectionSort(int arr[], int n)
{
int i, j, min_idx;

// One by one move boundary of

// unsorted subarray
for (i = 0; i < n - 1; i++) {

// Find the minimum element in

// unsorted array

min_idx = i;
EN21CS301878, YAMAN KUMAR SAHOO
 9

for (j = i + 1; j < n; j++) {

if (arr[j] < arr[min_idx])
min_idx = j;
}

// Swap the found minimum element

// with the first element
if (min_idx != i)
swap(arr[min_idx], arr[i]);
}
}

// Function to print an array

void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++) {
cout << arr[i] << " ";
cout << endl;
}
}
int main()
{
int arr[] = { 64, 25, 12, 22, 11 };
int n = sizeof(arr) / sizeof(arr[0]);

// Function Call
selectionSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}

OUTPUT:-

Sorted array:
11 12 22 25 64

EN21CS301878, YAMAN KUMAR SAHOO

 10

AIM: Write an algorithm and program to implement HEAP SORT.

ALGORITHM :-
1. HeapSort(arr)
2. BuildMaxHeap(arr)
3. for i = length(arr) to 2
4. swap arr[1] with arr[i]
5. heap_size[arr] = heap_size[arr] ? 1
6. MaxHeapify(arr,1)
7. End

PROGRAM :-
// C++ program for implementation of Heap Sort

#include <iostream>
using namespace std;

// To heapify a subtree rooted with node i

// which is an index in arr[].
// n is size of heap
void heapify(int arr[], int N, int i)
{

// Initialize largest as root

int largest = i;

// left = 2*i + 1
int l = 2 * i + 1;

// right = 2*i + 2
int r = 2 * i + 2;

// If left child is larger than root

if (l < N && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest
// so far
if (r < N && arr[r] > arr[largest])
largest = r;

if (largest != i) {
swap(arr[i], arr[largest]);
EN21CS301878, YAMAN KUMAR SAHOO
 11

// Recursively heapify the affected

// sub-tree
heapify(arr, N, largest);
}
}

// Main function to do heap sort

void heapSort(int arr[], int N)
{

// Build heap (rearrange array)

for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
for (int i = N - 1; i > 0; i--) {

// Move current root to end

swap(arr[0], arr[i]);

// call max heapify on the reduced heap

heapify(arr, i, 0);
}
}
void printArray(int arr[], int N)
{
for (int i = 0; i < N; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);

// Function call
heapSort(arr, N);

cout << "Sorted array is \n";

printArray(arr, N);
}

OUTPUT:-

Sorted array is
5 6 7 11 12 13

EN21CS301878, YAMAN KUMAR SAHOO

 12

AIM: Write an algorithm and program to implement RADIX SORT.

ALGORITHM :-
1. radixSort(arr)
2. max = largest element in the given array
3. d = number of digits in the largest element (or, max)
4. Now, create d buckets of size 0 - 9
5. for i -> 0 to d
6. sort the array elements using counting sort (or any stable sort) according to the
digits at the ith place

PROGRAM :-
// C++ implementation of Radix Sort

#include <iostream>
using namespace std;

// A utility function to get maximum

// value in arr[]
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}

// A function to do counting sort of arr[]

// according to the digit
// represented by exp.
void countSort(int arr[], int n, int exp)
{

// Output array
int output[n];
int i, count[10] = { 0 };

// Store count of occurrences

// in count[]
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;

EN21CS301878, YAMAN KUMAR SAHOO

 13

// Change count[i] so that count[i]

// now contains actual position
// of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];

// Build the output array

for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}

// The main function to that sorts arr[]

// of size n using Radix Sort
void radixsort(int arr[], int n)
{

// Find the maximum number to

// know number of digits
int m = getMax(arr, n);
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}

// A utility function to print an array

void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = { 543, 986, 217, 765, 329 };
int n = sizeof(arr) / sizeof(arr[0]);

// Function Call
radixsort(arr, n);
print(arr, n);
return 0;
}

OUTPUT:-

217 329 543 765 986

EN21CS301878, YAMAN KUMAR SAHOO

 14

AIM: Write an algorithm and program to implement BUCKET SORT.

ALGORITHM :-
Bucket Sort(A[])
1. Let B[0....n-1] be a new array
2. n=length[A]
3. for i=0 to n-1
4. make B[i] an empty list
5. for i=1 to n
6. do insert A[i] into list B[n a[i]]
7. for i=0 to n-1
8. do sort list B[i] with insertion-sort
9. Concatenate lists B[0], B[1],........, B[n-1] together in order
End

PROGRAM :-
// C++ program to sort an
// array using bucket sort
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Function to sort arr[] of

// size n using bucket sort
void bucketSort(float arr[], int n)
{

// 1) Create n empty buckets

vector<float> b[n];

// 2) Put array elements

// in different buckets
for (int i = 0; i < n; i++) {

// Index in bucket
int bi = n * arr[i];
b[bi].push_back(arr[i]);
}

EN21CS301878, YAMAN KUMAR SAHOO

 15

// 3) Sort individual buckets

for (int i = 0; i < n; i++)
sort(b[i].begin(), b[i].end());

// 4) Concatenate all buckets into arr[]

int index = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < b[i].size(); j++)
arr[index++] = b[i][j];
}

int main()
{
float arr[]
= { 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434 };
int n = sizeof(arr) / sizeof(arr[0]);
bucketSort(arr, n);

cout << "Sorted array is \n";

for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}

OUTPUT:-

Sorted array is
0.1234 0.3434 0.565 0.656 0.665 0.897

EN21CS301878, YAMAN KUMAR SAHOO

 16

AIM: Write an algorithm and program to implement MERGE SORT.

ALGORITHM :-
1. MERGE_SORT(arr, beg, end)
2.
3. if beg < end
4. set mid = (beg + end)/2
5. MERGE_SORT(arr, beg, mid)
6. MERGE_SORT(arr, mid + 1, end)
7. MERGE (arr, beg, mid, end)
8. end of if
9.
10. END MERGE_SORT

PROGRAM :-
// C++ program for Merge Sort
#include <bits/stdc++.h>
using namespace std;

void merge(int array[], int const left, int const mid,

int const right)
{
int const subArrayOne = mid - left + 1;
int const subArrayTwo = right - mid;

// Create temp arrays

auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];

// Copy data to temp arrays leftArray[] and rightArray[]

for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];

auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;

int indexOfMergedArray = left;

// Merge the temp arrays back into array[left..right]

while (indexOfSubArrayOne < subArrayOne
&& indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne]
EN21CS301878, YAMAN KUMAR SAHOO
 17

<= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}
while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}

// begin is for left index and end is right index

// of the sub-array of arr to be sorted
void mergeSort(int array[], int const begin, int const end)
{
if (begin >= end)
return;

int mid = begin + (end - begin) / 2;

mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}

void printArray(int A[], int size)

{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}

// Driver code
int main()
EN21CS301878, YAMAN KUMAR SAHOO
 18

{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

cout << "Given array is \n";

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\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

EN21CS301878, YAMAN KUMAR SAHOO

 19

AIM: Write an algorithm and program to implement QUICK SORT.

ALGORITHM :-
FOR SELECTING PIVOT
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot
FOR QUICK SORT
Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

PROGRAM :-
// C++ Implementation of the Quick Sort Algorithm.
#include <iostream>
using namespace std;

int partition(int arr[], int start, int end)

{

int pivot = arr[start];

int count = 0;
for (int i = start + 1; i <= end; i++) {
if (arr[i] <= pivot)
count++;
}
// Giving pivot element its correct position
int pivotIndex = start + count;
swap(arr[pivotIndex], arr[start]);

// Sorting left and right parts of the pivot element

int i = start, j = end;

while (i < pivotIndex && j > pivotIndex) {

while (arr[i] <= pivot) {

i++;
}

EN21CS301878, YAMAN KUMAR SAHOO

 20

while (arr[j] > pivot) {

j--;
}

if (i < pivotIndex && j > pivotIndex) {

swap(arr[i++], arr[j--]);
}
}

return pivotIndex;
}
void quickSort(int arr[], int start, int end)
{

// base case
if (start >= end)
return;

// partitioning the array

int p = partition(arr, start, end);

// Sorting the left part

quickSort(arr, start, p - 1);

// Sorting the right part

quickSort(arr, p + 1, end);
}

int main()
{

int arr[] = { 9, 3, 4, 2, 1, 8 };
int n = 6;
quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";
}

return 0;
}

OUTPUT:-
1 2 3 4 8 9

EN21CS301878, YAMAN KUMAR SAHOO