Experiment: 1

Aim: Write a program of Bubble Sort.

Algorithm
begin BubbleSort(arr)
for all array elements
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
end BubbleSort

Code
#include <iostream>
using namespace std;
void bS(int ar[], int size)
{
for (int step = 0; step < size; ++step)
{
for (int i = 0; i < size - step; ++i)
{
if (ar[i] > ar[i + 1])
{
int temp = ar[i];
ar[i] = ar[i + 1];
 ar[i + 1] = temp;
}
}
}
}
void printAr(int ar[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << ar[i];
}
cout << "\n";
}
int main()
{
int data[] = {2, 45, 0, 11, 9};
int size = sizeof(data) / sizeof(data[0]);
bS(data, size);
cout << "Sorted Array in Ascending Order:\n";
printAr(data, size);
return 0;
}

Output:
 Experiment: 2
Aim: Write a program of Selection Sort.
Selection Sort
In selection sort, the smallest value among the unsorted elements of the array is selected in
every pass and inserted to its appropriate position into the array. It is also the simplest
algorithm. It is an in-place comparison sorting algorithm. In this algorithm, the array is
divided into two parts, first is sorted part, and another one is the unsorted part. Initially, the
sorted part of the array is empty, and unsorted part is the given array. Sorted part is placed
at the left, while the unsorted part is placed at the right.
The average and worst-case complexity of selection sort is O(n2), where n is the number of
items. Due to this, it is not suitable for large data sets.

Algorithm
1. SELECTION SORT(arr, n)
2.
3. Step 1: Repeat Steps 2 and 3 for i = 0 to n-1
4. Step 2: CALL SMALLEST(arr, i, n, pos)
5. Step 3: SWAP arr[i] with arr[pos]
6. [END OF LOOP]
7. Step 4: EXIT
8.
9. SMALLEST (arr, i, n, pos)
10. Step 1: [INITIALIZE] SET SMALL = arr[i]
11. Step 2: [INITIALIZE] SET pos = i
12. Step 3: Repeat for j = i+1 to n
13. if (SMALL > arr[j])
14. SET SMALL = arr[j]
15. SET pos = j
16. [END OF if]
17. [END OF LOOP]
18. Step 4: RETURN pos
 Code
#include<iostream>
using namespace std;
void sel(int arr[], int n)
{
int i,j,small;
for (i = 0; i < n-1; i++)
{
small = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[small])
small = j;
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
}
}
void printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
cout<< a[i] <<" ";
}
int main()
{
int a[] = { 80, 10, 29, 11, 8, 30, 15 };
int n = sizeof(a) / sizeof(a[0]);
 cout<< "Before sorting :- "<<endl;
printArr(a, n);
sel(a, n);
cout<< "\nAfter sorting :- "<<endl;
printArr(a, n);

return 0;
}

Output:
 Experiment: 3
Aim: Write a program of Merge Sort.
Merge Sort
Merge sort is similar to the quick sort algorithm as it uses the divide and conquer approach
to sort the elements. It is one of the most popular and efficient sorting algorithm. It divides
the given list into two equal halves, calls itself for the two halves and then merges the two
sorted halves. We have to define the merge() function to perform the merging.

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

Code
#include <iostream>
using namespace std;
void Merge(int *a, int low, int high, int mid)
{
int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
}
while (j <= high)
{
temp[k] = a[j];
k++;
j++;
}
for (i = low; i <= high; i++)
{
a[i] = temp[i-low];
 }
}
void MergeSort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
Merge(a, low, high, mid);
}
}

int main()
{
int n, i;
cout<<"\nEnter the total no. to be sorted: ";
cin>>n;

int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter the no. "<<i+1<<": ";
cin>>arr[i];
}

MergeSort(arr, 0, n-1);
cout<<"\nSorted no's are ";
 for (i = 0; i < n; i++)
cout<<","<<arr[i];

return 0;
}

Output:
 Experiment: 4
Aim: Write a program of Insertion Sort.
Insertion Sort
Insertion sort works similar to the sorting of playing cards in hands. It is assumed that the
first card is already sorted in the card game, and then we select an unsorted card. If the
selected unsorted card is greater than the first card, it will be placed at the right side;
otherwise, it will be placed at the left side. Similarly, all unsorted cards are taken and put in
their exact place.
The same approach is applied in insertion sort. The idea behind the insertion sort is that first
take one element, iterate it through the sorted array. Although it is simple to use, it is not
appropriate for large data sets as the time complexity of insertion sort in the average case
and worst case is O(n2), where n is the number of items. Insertion sort is less efficient than
the other sorting algorithms like heap sort, quick sort, merge sort, etc.

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.

Code
#include <iostream>
using namespace std;
void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
 a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main() {
int a[] = {12, 1, 10, 5, 8, 7, 6, 9};
int n = sizeof(a) / sizeof(a[0]);
cout << "Unsorted array: " << endl;
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
insertionSort(a, n);
cout << "Sorted array: " << endl;
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;

return 0;
}

Output:
 Experiment: 5
Aim: Write a program of Binary search.
Binary Search
Binary search is the search technique that works efficiently on sorted lists. Hence, to search
an element into some list using the binary search technique, we must ensure that the list is
sorted.

Binary search follows the divide and conquer approach in which the list is divided into two
halves, and the item is compared with the middle element of the list. If the match is found
then, the location of the middle element is returned. Otherwise, we search into either of the
halves depending upon the result produced through the match.

Algorithm (Recursive)
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] // x is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the left side
return binarySearch(arr, x, low, mid - 1)

Code (Recursive)
#include <iostream>
using namespace std;

int bs(int array[],int x,int low,int high) {

if (array[mid]>x)
return bs(array,x,low,mid - 1);
return bs(array, x,mid + 1,high);
}
return 0;
}
int main() {
int array[]={43,48,59,76,78,98,90}
;
int x=76;
int n =sizeof(array)/sizeof(array[0]);
int result = bs(array,x,0,n-1);
if (result == 0)
printf("Not found");
else
printf("Element is found at index %d", result);
}

Output:
 Algorithm (Iteration)
do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1

Code (Iteration)
#include <iostream>
using namespace std;
int binarySearch(int array[], int x, int low, int high)
{
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int x = 4;
int n = sizeof(array) / sizeof(array[0]);
 int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
}

Output:
 PROGRAM 6
AIM: Sort a array using Merge Sort.

Introduction:-

Merge sort is defined as a sorting algorithm that works by dividing an array

Algorithm:-
Algo ms(low,high){
If(low<high)
{mid=low+high/2;
ms(low,mid);
ms(mid+1,high);

merge(low,mid,high);
}
Algo merge(low,mid,high)
{
H=low; i=low; j=mid+1;
While((high<=mid)&&(j<=high))
{
if(a[h]<=a[j]
{ b[i]=a[h];
h++;
}
else{
b[i]=a[i];
j++;
}i++;
}
If(h>mid){
for(k=I;k<=high;k++
{

b[i]=a[k]
i++;
}
else{
for(k=h;k<=mid;k++){
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++){
a[k]=b[k];
}}

Implementation:-
#include <iostream>
using namespace std;
void marge(int*arr,int s,int e){
int mid=s+(e-s)/2;
int len1=mid-s+1;
int len2=e-mid;
int *left =new int[len1];
int *right =new int[len2];
//copy left value
int k=s;
for(int i=0;i<len1;i++){
left[i]=arr[k];
k++;
}
//copy right value
k=mid+1;
for(int i=0;i<len2;i++){
right[i]=arr[k];
k++;
}
//merge logic
int leftindex=0;
int rightoindex=0;
int mainarrindex=s;
while (leftindex<len1 && rightoindex<len2){
if(left[leftindex]<=right[rightoindex]){
 arr[mainarrindex]=left[leftindex];
mainarrindex++;
leftindex++;
}
else{
arr[mainarrindex]=right[rightoindex];
mainarrindex++;
rightoindex++;
}
}
//copy lrft array
while (leftindex<len1){
arr[mainarrindex]=left[leftindex];
mainarrindex++;
leftindex++;
}
//copy right array
while(rightoindex<len2){
arr[mainarrindex]=right[rightoindex];
mainarrindex++;
rightoindex++;
}
}
void mergesor(int*arr,int s,int e){
if(s>=e){
return ;
}
int mid=s+(e-s)/2;
//left part sort
mergesor(arr,s,mid);
//right sort
mergesor(arr,mid+1,e);

marge(arr,s,e);
}
int main() {
int arr[]={22,37,13,12,21,62};
int size =6;
 int s=0;
int e=size-1;
mergesor(arr,s,e);
cout<<"sorted array:";
for(int i=0;i<size;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}

Output:-