Searching And Sorting

[jason9]

I couldn't really find a good example of the various searching and sorting algorithms out there so i figured i would post one i did for an assignment.

The number of comparisons done may not be done quite right but it definitely gives you the idea of which ones are more efficient.

main.cpp

#include <iostream>
#include "SearchAndSort.h"

using namespace std;

void main()
{
	//initilizes the varibles to store the number of comparisons
	int linearSearchComp=0;
	int binarySearchComp=0;
	int insertionSortComp=0;
	int selectionSortComp=0;
	int bubbleSortComp=0;
	int mergeSortComp=0;

	for(int i = 0; i < 50; i++) //runs 50 instances of the various sorting and seraching methods on data
	{
		SearchAndSort arr;
		cout << "Initial Conditions" << endl;
		arr.print();

		cout << endl << "After Linear Search" << endl;
		linearSearchComp = linearSearchComp + arr.linearSearch(50);
		arr.print();

		cout << endl << "After Binary Search" << endl;
		binarySearchComp = binarySearchComp + arr.binarySearch(50);
		arr.print();

		cout << endl << "After Insertion Sort" << endl;
		insertionSortComp = insertionSortComp + arr.insertionSort();
		arr.print();

		cout << endl << "After Selection Sort" << endl;
		selectionSortComp = selectionSortComp + arr.selectionSort();
		arr.print();
		
		cout << endl << "After Bubble Sort" << endl;
		bubbleSortComp = bubbleSortComp + arr.bubbleSort();
		arr.print();

		cout << endl << "After Merge Sort" << endl;
		mergeSortComp = mergeSortComp + arr.mergeSort();
		arr.print();
	}

	//detemines the average amount of comparisons for that are used for each searching and sorting algorithms
	linearSearchComp = linearSearchComp / 50;
	binarySearchComp = binarySearchComp / 50;
	insertionSortComp = insertionSortComp / 50;
	selectionSortComp = selectionSortComp / 50;
	bubbleSortComp = bubbleSortComp / 50;
	mergeSortComp = mergeSortComp / 50;

	//outputs the averge number of comparisons performed for each searching and sorting algorithms
	cout << "Average Number of Comparisons for Linear Search " << linearSearchComp << endl;
	cout << "Average Number of Comparisons for Binary Search " << binarySearchComp << endl;
	cout << "Average Number of Comparisons for Insertion Sort " << insertionSortComp << endl;
	cout << "Average Number of Comparisons for Selection Sort " << selectionSortComp << endl;
	cout << "Average Number of Comparisons for Bubble Sort " << bubbleSortComp << endl;
	cout << "Average Number of Comparisons for Merge Sort " << mergeSortComp << endl;

	system("pause");
}

[jason9]

SearchAndSort.h

#ifndef SEARCH_AND_SORT_H
#define SEARCH_AND_SORT_H

class SearchAndSort
{
public:
	SearchAndSort();
	void prepareArr();
	void copyArr();
	void print();
	int linearSearch(int); //takes in key for search and returns number of comparisons
	int binarySearch(int); //takes in key for search and returns number of comparisons
	int insertionSort(); //returns number of comparisons
	int selectionSort(); //returns number of comparisons
	int bubbleSort(); //returns number of comparisons
	int mergeSort(); //returns number of comparisons

private:
	static const int size = 100;
	int initialArr[size];
	int sortResult[size];
	int searchResult;
	int mergeSortReccur(int,int); //recursive funtion used for merge sort
	int merge(int,int,int,int); //utility function for the merge sort that merges two sub arrays
};

#endif 

SearchAndSort.cpp

#include "SearchAndSort.h"

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <ctime>

using namespace std;

SearchAndSort::SearchAndSort()
{
	prepareArr();
	copyArr();
}

void SearchAndSort::prepareArr() //fill an array with 100 elements with random values from 0 to 100
{
	srand(time(0)); //time is used as the random seed
	for(int i = 0; i <= size-1;  i++)
	{
		initialArr[i] = rand() % 101; //assigns random number in array
	}
}

void SearchAndSort::copyArr() //copies the values stored in initial array to the sorted result array
{
	for(int i = 0; i <= size-1;  i++)
	{
		sortResult[i] = initialArr[i]; //copies element by element
	}
}

void SearchAndSort::print() //outputs the initial array, sorted result array, and search result
{
	cout << "Initial Array" << endl;
	for(int i = 0; i <= size-1;  i++)
	{
		cout << initialArr[i] << " ";
	}
	cout << endl;

	cout << "Sorted Result Array" << endl;
	for(int i = 0; i <= size-1;  i++)
	{
		cout << sortResult[i] << " ";
	}
	cout << endl;

	cout << "Search Result" << endl;
	cout << searchResult << endl;
}

int SearchAndSort::linearSearch(int key)
{
	copyArr();
	int comparisons = 0;
	searchResult = -1;
	for(int i = 0; i <= size-1; i++) //cycles through each element in the array
	{
		comparisons++;
		if(key == initialArr[i]) //if the value in array matches key then position is stored
		{
			searchResult = i;
			break; //breaks once values is found in array
		}
	}
	return comparisons;
}

int SearchAndSort::binarySearch(int key)
{
	mergeSort(); //binary search requires that the array be sorted before search
	int low = 0;
	int high = size -1;
	int mid = (low + high + 1) / 2;
	int loc = -1;
	int comparisons = 0;

	do{
		if(key == sortResult[mid]) //checks to see if the middle value is equal to the key
		{
			loc = mid; //if so the location is set to middle position
			comparisons++;
		}
		else if(key > sortResult[mid]) //if key is greater than the mid point then the key value must be in the first half of the array if it exists at all
		{
			high = mid - 1; //make the new right bound of array to the left of the midpoint
			comparisons++;
		}
		else //if key is less than the mid point then the key value must be in the second half of the array if it exists at all
		{
			low = mid + 1; //make the new left bound of the array to the right of the midpoint
			comparisons++;
		}

		mid = (low + high + 1) / 2; // the new bid is determined from the new high and low
	}while((low <= high) && (loc == -1)); //runs as long the key has not been found and low does not become greater than high
	
	searchResult = loc;

	return comparisons;
}

int SearchAndSort::insertionSort()
{
	copyArr();

	int j, insert = 0, comparisons = 0;
	for(int i = 1; i <= size-1; i++)
	{
		comparisons++;
		insert = sortResult[i];
		for( j = i - 1; (j >= 0) && (sortResult[j] < insert); j--) //smaller values move up in the array 
		{
			comparisons++;
			sortResult[j+1] = sortResult[j];
		}
		sortResult[j+1] = insert; //put the inserted value in the its the right place to be sorted
	}
	return comparisons;
}

int SearchAndSort::selectionSort()
{
	copyArr();

	int comparisons = 0;
	int first;

	for(int i = size-1; i > 0; i--)
	{
		comparisons++;
		first = 0;
		for(int j = 1; j <= i; j++) //locates smallest between 1 and i
		{
			comparisons++;
			if(sortResult[j] < sortResult[first])
			{
				first = j;
				comparisons++;
			}
		}
		int temp = sortResult[first]; //swaps the smallest with the element in position i
		sortResult[first] = sortResult[i];
		sortResult[i] = temp;
	}
	return comparisons;
}


int SearchAndSort::bubbleSort()
{
	copyArr();
	int comparisons = 0;
	for(int i = 0; i < size-1; i++)
	{
		comparisons++;
		for(int j = 0; j < size-1; j++)
		{
			comparisons++;
			if(sortResult[j+1] > sortResult[j]) //if next element is greater than the current element then swap elements
			{
				comparisons++;
				int temp = sortResult[j]; //swaps the elements
				sortResult[j] = sortResult[j+1];
				sortResult[j+1] = temp;
			}
		}
	}
	return comparisons;
}

int SearchAndSort::mergeSort()
{
	copyArr();
	return mergeSortReccur(0,size-1);  //calls the merge sort recursive function and returns the number of comparisons
}

int SearchAndSort::mergeSortReccur(int low, int high)
{
	int comparisons = 0;
	int mid = 0;
	if((high - low) >= 1)
	{
		comparisons++;
		mid = ((low + high) / 2); 
		mergeSortReccur(low, mid); //runs recursive function with first half of array
		mergeSortReccur(mid+1, high); //runs recursive function with second half of the array
		comparisons = comparisons + merge(low, mid, mid+1, high); //call the merge and totals the number of comparisons
	}
	return comparisons;
}

int SearchAndSort::merge(int left, int mid1, int mid2, int right) //merges two sub arrays
{
	int leftIndex = left;
	int rightIndex = mid2;
	int combinedIndex = left;
	int combined[size];
	int comparisons = 0;

	while(leftIndex <= mid1 && rightIndex <= right) //merge arrays until the end of the either array
	{
		comparisons++;
		//places larger of the two current elements into the resulting combined array
		if(sortResult[leftIndex] >= sortResult[rightIndex])
		{
			comparisons++;
			combined[combinedIndex++] = sortResult[leftIndex++];
		}else
		{
			comparisons++;
			combined[combinedIndex++] = sortResult[rightIndex++];
		}
	}

	if(leftIndex == mid2) //if the left array is at end
	{
		comparisons++;
		while(rightIndex <= right) //copy the remaining elements in the right array
		{
			comparisons++;
			combined[combinedIndex++] = sortResult[rightIndex++];
		}
	}else //if the right array is at end 
	{
		comparisons++;
		while(leftIndex <= mid1) //copy the remaing elements in the left array
		{
			comparisons++;
			combined[combinedIndex++] = sortResult[leftIndex++];
		}
	}

	//copies values back in the original result array
	for(int i = left; i <= right; i++)
		sortResult[i] = combined[i];

	return comparisons;
}