-
Notifications
You must be signed in to change notification settings - Fork 0
/
BubbleSort.cpp
160 lines (121 loc) · 3.22 KB
/
BubbleSort.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
/*
Lucy Tran
9 - 19 - 16
Function File : Bubble Sort Class
PA1 : Bubblesort
+ public
- private
*Contains vector, size of vector = n
*Member Functions: +removeVectorElements, +generateVectors, -generateVectorsHelper, -generateInorder, -generateReverse, -generateRandom, -randomGenerator
*Non-member Functions:
*/
#include "BubbleSort.h"
/*Constructors*/
BubbleSort::BubbleSort() {
_n = 0;
}
//N = size of vector
BubbleSort::BubbleSort(const int & n) {
////http://www.cplusplus.com/reference/vector/vector/vector/
//vector<int> v(n); //N ints with the value 0
//_v = v;
_n = n;
}
/*Destructor*/
BubbleSort::~BubbleSort() {}
/*Getters*/
int const & BubbleSort::getN() const {
return _n;
}
/*Setters*/
void BubbleSort::setN(int & newN) {
_n = newN;
}
/*Public Functions*/
//Fills vector with values according to the indicator
void BubbleSort::generateVectors(int vectorIndicator) {
generateVectorsHelper(vectorIndicator);
}
// sorts the vector of n elements passed in
// returns # of seconds to accomplish the sorting
float BubbleSort::doBubbleSort() {
int temp = 0; //temporary variable for swapping
//BubbleSort
//Refer to: http://mathbits.com/MathBits/CompSci/Arrays/Bubble.htm, http://www.algolist.net/Algorithms/Sorting/Bubble_sort
//Measuring time
//Refer to: http://en.cppreference.com/w/cpp/chrono
time_point<system_clock> start, end; //start timer
start = system_clock::now();
if (!_v.empty()) //Check if vector is empty
{
for (int i = 0; i < _n; i++) {
for (int j = 0; j < _n - i - 1; j++) {
//Ascending order
if (_v[j] > _v[j + 1]) {
//Swap
temp = _v[j];
_v[j] = _v[j + 1];
_v[j + 1] = temp;
}
}
}
end = std::chrono::system_clock::now(); //end timer
duration<float> elapsedSecs = end - start; //Calculate seconds
return elapsedSecs.count();
}
else
{
return -1;
}
}
//Removes all vector elements
void BubbleSort::removeVectorElements() {
//Refer to: http://www.cplusplus.com/reference/vector/vector/pop_back/
while (!_v.empty()) {
_v.pop_back();
}
}
/*Private Functions*/
//Fills vector with values according to the indicator
void BubbleSort::generateVectorsHelper(int vectorIndicator) {
//Vector that is ordered
if (vectorIndicator == OPTIMAL) {
generateInorder();
}
//Vector in reverse order
else if (vectorIndicator == AVERAGE) {
generateRandom();
}
else {
generateReverse();
}
}
//Fills a vector with values in order
void BubbleSort::generateInorder() {
for (int i = 0; i < _n; i++) {
_v.push_back(i); //Adds a new value (i)
}
}
//Fills a vector with values in reverse order
void BubbleSort::generateReverse() {
for (int i = _n; i > 0; i--) {
_v.push_back(i); //Adds a new value (i)
}
}
//Fills a vector with random values [0, 100]
void BubbleSort::generateRandom() {
//Generate N random values
for (int i = 0; i < _n; i++)
{
_v.push_back(randomGenerator()); //Adds a new random value
}
}
//Generates a random number from 0 - 100
int BubbleSort::randomGenerator() {
//Refer to: http://www.cplusplus.com/reference/cstdlib/rand/ , http://stackoverflow.com/questions/5008804/generating-random-integer-from-a-range
//initialize random seed:
srand(time(NULL));
//generate number between 0 and 100:
int x = (rand() % (101));
return x;
}