### Searching And Sorting 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
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364`` ``````#include #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"); }`````` SearchAndSort.h
 ``123456789101112131415161718192021222324252627`` ``````#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
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240`` ``````#include "SearchAndSort.h" #include #include #include #include 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; }``````

Topic archived. No new replies allowed.