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;
}
|
