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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
|
#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");
}
| |
SearchAndSort.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
#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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240
|
#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;
}
| |