1446

DESIGN AND ANALYSIS OF

SORT PROGRAM AND BINARY SEARCH

| SH.A.AL
BINARY SEARCH ………………………… 1
Iterative Implementation ………………………… 1

Recursive Implementation ……………………….. 2

Merge Sort ………………………………… 3

Bubble sort ………………………………… 8

Iterative Implementation
#include <bits/stdc++.h>
using namespace std;
// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x) {
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was not present
return -1;
}
// Driver code
int main() {
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
cout << "Element is not present in array";
else
cout << "Element is present at index " << result;

return 0;
}

1
Recursive Implementation
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function.
// It returns location of x in given array arr[low..high] if
present,
// otherwise -1.
int binarySearch(int arr[], int low, int high, int x) {
if (high >= low) {
int mid = low + (high - low) / 2;
// If the element is present at the middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, it can only be present
in left subarray
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
// Else the element can only be present in right subarray
return binarySearch(arr, mid + 1, high, x);
}
// We reach here if the element is not present in the array
return -1;
}
// Driver code
int main() {
int arr[] = {2, 3, 4, 10, 40};
int query = 90;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, query);
if (result == -1)
cout << "Element is not present in array";
else
cout << "Element is present at index " << result;
return 0;
}

2
Merge Sort
#include <bits/stdc++.h>
using namespace std;
// Merges two subarrays of arr[].
// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temp vectors
vector<int> L(n1), R(n2);
// Copy data to temp vectors L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int k = left;
// Merge the temp vectors back into arr[left..right]
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

3
// left is for left index and right is right index of the sub-array
of arr to be sorted
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right)
return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
// Function to print a vector
void printVector(vector<int>& arr) {
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver code
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
int n = arr.size();
cout << "Given vector is \n";
printVector(arr);
mergeSort(arr, 0, n - 1);
cout << "\nSorted vector is \n";
printVector(arr);
return 0;
}

4
Quick sort
#include <iostream>
using namespace std;
// function to swap elements
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// function to print the array
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// function to rearrange array (find the partition point)
int partition(int array[], int low, int high) {
// select the rightmost element as pivot
int pivot = array[high];
// pointer for greater element
int i = (low - 1);
// traverse each element of the array
// compare them with the pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;
// swap element at i with element at j
swap(&array[i], &array[j]);
}
}
// swap pivot with the greater element at i
swap(&array[i + 1], &array[high]);
// return the partition point
return (i + 1);
}

5
void quickSort(int array[], int low, int high) {
if (low < high) {
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on righ of pivot
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
// Driver code
int main() {
int data[] = {8, 7, 6, 1, 0, 9, 2};
int n = sizeof(data) / sizeof(data[0]);
cout << "Unsorted Array: \n";
printArray(data, n);
// perform quicksort on data
quickSort(data, 0, n - 1);
cout << "Sorted array in ascending order: \n";
printArray(data, n);
}

6
Insertion Sort
#include <iostream>
using namespace std;
/* Function to sort array using insertion sort */
void insertionSort(int arr[], int n)
{
for (int i = 1; i < n; ++i) {
int key = arr[i];
int 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;
}
arr[j + 1] = key;
}
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << endl;
}
// Driver method
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Array before sorting: \n";
printArray(arr, n);
insertionSort(arr, n);
cout << "Array after sorting: \n";
printArray(arr, n);
return 0;
}

7
Bubble sort
#include <bits/stdc++.h>
using namespace std;
void bubbleSort(vector<int>& v) {
int n = v.size();
// Outer loop that corresponds to the number of
// elements to be sorted
for (int i = 0; i < n - 1; i++) {
// Last i elements are already
// in place
for (int j = 0; j < n - i - 1; j++) {
// Comparing adjacent elements
if (v[j] > v[j + 1])
// Swapping if in the wrong order
swap(v[j], v[j + 1]);
}
}
}
int main() {
vector<int> v = {5, 1, 4, 2, 8};
cout << "Before sorting: \n";
for (auto i : v)
cout << i << " ";
cout << endl;
// Sorting the vector v
bubbleSort(v);
cout << "After sorting: \n";
for (auto i : v)
cout << i << " ";
return 0;
}

SH.A.AL
8