PrintArray.cpp

#include "pch.h"
#include <iostream>
#include "PrintArray.h"

using namespace std;


PrintArray::PrintArray()
{
}


PrintArray::~PrintArray()
{
}

void PrintArray::PrintArrayFunc(int *arr, int n)
{
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << "\n";
}

PrintArray.h

#pragma once
class PrintArray
{
private:
	PrintArray();
	~PrintArray();

public:
	static void PrintArrayFunc(int *arr, int n);
};

Searching.cpp

#include "pch.h"
#include <iostream>
#include "Searching.h"
#include "math.h"
#include <algorithm>

using namespace std;


Searching::Searching()
{
}


Searching::~Searching()
{
}

int Searching::BinarySearch(int *arr, int left, int right, int x)
{
	if (right >= left)
	{
		int mid = left + (right - left) / 2;

		if (arr[mid] == x)
		{
			return mid;
		}

		if (arr[mid] > x)
			return BinarySearch(arr, left, mid - 1, x);
		else
			return BinarySearch(arr, mid + 1, right, x);
	}

	return -1;
}

int Searching::JumpSearch(int *arr, int x, int n)
{
	int step = sqrt(n);
	int prev = 0;

	while (arr[min(step, n) - 1] < x)
	{
		prev = step;
		step += sqrt(n);
		if (prev > n)
			return -1;
	}
	while (arr[prev]<x)
	{
		prev++;
		if (prev == min(step, n))
			return -1;
	}
	if (arr[prev]==x)
		return prev;

	return -1;
}

int Searching::InterpolationSearch(int *arr, int n, int x)
{
	int low = 0, high = (n -1);

	while (low <= high && x >= arr[low] && x <= arr[high])
	{
		int position = low + (((double)(high - low) / (arr[high] - arr[low])) * (x - arr[low]));

		if (arr[position] == x)
			return position;
		if (arr[position] < x)
			low= position + 1;
		else
			high = position - 1;
	}
	return -1;

}

int Searching::ExponentialSearch(int *arr, int n, int x)
{
	if (arr[0] == x)
		return 0;

	int i = 1;
	while (i < n && arr[i] <= x)
		i = i*2;

	return BinarySearch(arr, i/2, min(i, n), x);
}

Searching.h

#pragma once
class Searching
{
private:
	Searching();
	~Searching();

public:
	static int BinarySearch(int *arr, int left, int right, int x);
 	static int JumpSearch(int *arr, int x, int n);
 	static int InterpolationSearch(int *arr, int n, int x);
 	static int ExponentialSearch(int *arr, int n, int x);
};

SortAndSearch.cpp

#include "pch.h"
#include <iostream>
#include "Sorting.h"
#include "Searching.h"
#include "PrintArray.h"

using namespace std;

int main()
{
	// The array
	int arr[] = { 2, 4, 1, 5, 6, 3 };
	// The mid element of arr[]
	int n = sizeof(arr) / sizeof(arr[0]);
	// Number seasrched for in the array arr[]
	int x = 4;

	printf("Given array is \n");
	PrintArray::PrintArrayFunc(arr, n);

// ------SORT FUNCTIONS-------

// --------QuickSort----------
	Sorting::QuickSort(arr, 0, n - 1);

// --------InsertSort---------
/*	Sorting::InsertSort(arr, n);*/

// --------SelectionSort------
/*	Sorting::SelectSort(arr, n);*/

// --------MergeSort----------
/*	Sorting::MergeSort(arr, 0, n);/ *0, sizeof(arr) - 1);* /*/

// --------BubbleSort---------
/*	Sorting::BubbleSort(arr, n); */

// --------HeapSort-----------
//	Sorting::HeapSort(arr, n);

	cout << "Sorted array is \n";
	PrintArray::PrintArrayFunc(arr, n);

// ------SEARCH FUNCTIONS------

// -----ExponentialSearch-----
	int result = Searching::ExponentialSearch(arr, n, x);
	(result == -1) ? printf("Element is not present in array")
		: printf("Element is present at index %d", result);

// ----InterpolationSearch----
// 	int result = Searching::InterpolationSearch(arr, n, x);
// 	(result == -1) ? printf("Element is not present in array")
// 		: printf("Element is present at index %d", result);

// --------JumpSearch---------
// 	int result = Searching::JumpSearch(arr, x, n);
// 	(result == -1) ? printf("Element is not present in array")
// 		: printf("Element is present at index %d", result);


// --------BinarySearch-------
// 	int result = Searching::BinarySearch(arr, 0, n - 1, x);
// 	(result == -1) ? printf("Element is not present in array")
// 		: printf("Element is present at index %d",
// 			result);

	return 0;
}

SortAndSearch.sln

Microsoft Visual Studio Solution File, Format Version 12.00
# Visual Studio 15
VisualStudioVersion = 15.0.28010.2016
MinimumVisualStudioVersion = 10.0.40219.1
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "SortAndSearch", "SortAndSearch\SortAndSearch.vcxproj", "{661EA1E3-2A4E-410D-A2E0-92F43EAD1495}"
EndProject
Global
	GlobalSection(SolutionConfigurationPlatforms) = preSolution
		Debug|x64 = Debug|x64
		Debug|x86 = Debug|x86
		Release|x64 = Release|x64
		Release|x86 = Release|x86
	EndGlobalSection
	GlobalSection(ProjectConfigurationPlatforms) = postSolution
		{661EA1E3-2A4E-410D-A2E0-92F43EAD1495}.Debug|x64.ActiveCfg = Debug|x64
		{661EA1E3-2A4E-410D-A2E0-92F43EAD1495}.Debug|x64.Build.0 = Debug|x64
		{661EA1E3-2A4E-410D-A2E0-92F43EAD1495}.Debug|x86.ActiveCfg = Debug|Win32
		{661EA1E3-2A4E-410D-A2E0-92F43EAD1495}.Debug|x86.Build.0 = Debug|Win32
		{661EA1E3-2A4E-410D-A2E0-92F43EAD1495}.Release|x64.ActiveCfg = Release|x64
		{661EA1E3-2A4E-410D-A2E0-92F43EAD1495}.Release|x64.Build.0 = Release|x64
		{661EA1E3-2A4E-410D-A2E0-92F43EAD1495}.Release|x86.ActiveCfg = Release|Win32
		{661EA1E3-2A4E-410D-A2E0-92F43EAD1495}.Release|x86.Build.0 = Release|Win32
	EndGlobalSection
	GlobalSection(SolutionProperties) = preSolution
		HideSolutionNode = FALSE
	EndGlobalSection
	GlobalSection(ExtensibilityGlobals) = postSolution
		SolutionGuid = {C75C5CEC-751F-4784-ABFD-0E99C37BF079}
	EndGlobalSection
EndGlobal

Sorting.cpp

#include "pch.h"
#include "Sorting.h"
#include <algorithm>

using namespace std;

Sorting::Sorting()
{
}


Sorting::~Sorting()
{
}

void Sorting::Heapify(int *arr, int n, int i)
{
	int large = i;
	int left = 2 * i + 1;
	int right = 2 * i + 2;

	if (left < n && arr[left] > arr[large])
		large = left;

	if (right < n && arr[right] > arr[large])
		large = right;

	if (large != i)
	{
		swap(arr[i], arr[large]);
		Heapify(arr, n, large);
	}
}

void Sorting::HeapSort(int *arr, int n)
{
	for (int i = n / 2 - 1; i >= 0; i--)
		Heapify(arr, n, i);

	for (int i = n - 1; i >= 0; i--)
	{
		swap(arr[0], arr[i]);
		Heapify(arr, i, 0);
	}
}

void Sorting::Swapping(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

void Sorting::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])
			{
				Swapping(&arr[j], &arr[j+1]);
				swapped = true;
			}
		}
		if (swapped == false)
			break;
	}
}

void Sorting::Merge(int *arr, int left, int middle, int right)
{
	int i, j, mi;
	int n1 = middle - left;
	int n2 = right - middle + 1;

	int*  L;
	int* R;
	L = new int [n1];
	R = new int [n2];

	for (i = 0; i < n1; i++)
		L[i] = arr[left + i];
	for (j = 0; j < n2; j++)
		R[j] = arr[middle + 1 + j];

	i = 0;
	j = 0;
	mi = left;

	while (i < n1 && j < n2)
	{
		if (L[i] <= R[j])
		{
			arr[mi] = L[i];
			i++;
		}
		else
		{
			arr[mi] = R[j];
			j++;
		}
		mi++;
	}
	while (i < n1)
	{
		arr[mi] = L[i];
		i++;
		mi++;
	}
	while (j < n2)
	{
		arr[mi] = R[j];
		j++;
		mi++;
	}
}

void Sorting::MergeSort(int *arr, int left, int right)
{
	if (left < right)
	{
		int middle = (left+right)/2;
		MergeSort(arr, left, middle);
		MergeSort(arr, middle+1, right);
		Merge(arr, left, middle, right);
	}
} 

void Sorting::SelectSort(int *arr, int n)
{
	int i, j, minidx;

	for (i = 0; i < n - 1; i++)
	{
		minidx = i;
		for (j = i + 1; j < n; j++)
			if (arr[j] < arr[minidx])
				minidx = j;

		Swapping(&arr[minidx], &arr[i]);
	}
}

void Sorting::InsertSort(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 Sorting::Partition(int *arr, int low, int high)
{
	int pivot = arr[high]; // pivot point
	int i = (low - 1); // index for smaller elements

	for (int j = low; j <= high - 1; j++)
	{
		if (arr[j] < pivot)
		{
			i++;
			Swapping(&arr[i], &arr[j]);
		}
	}
	Swapping(&arr[i + 1], &arr[high]);
	return (i+1);
}

void Sorting::QuickSort(int *arr, int low, int high)
{
	if (low < high)
	{
		int partidx = Partition(arr, low, high);
		QuickSort(arr, low, partidx - 1);
		QuickSort(arr, partidx + 1, high);
	}
}

Sorting.h

#pragma once
class Sorting
{
private:
	Sorting();
	~Sorting();

public:
	static void Heapify(int *arr, int n, int i);
	static void HeapSort(int *arr, int n);
	static void Swapping(int *xp, int *yp);
	static void BubbleSort(int *arr, int n);
	static void Merge(int *arr, int left, int middle, int right);
	static void MergeSort(int *arr, int left, int right);
	static void SelectSort(int *arr, int n);
	static void InsertSort(int *arr, int n);
	static int Partition (int *arr, int low, int high);
	static void QuickSort(int *arr, int low, int high);
};