commit 0d377147973d284c443ccd7947710c429499db66
parent 66c90810805c4579c7e829944244b7604a5535b4
Author: William Lindholm <a22willi@student.his.se>
Date: Wed, 29 Nov 2023 13:22:29 +0100
Added empirical measurements functionality.
Diffstat:
| M | Problem1/Problem1.cpp | | | 102 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------- |
1 file changed, 85 insertions(+), 17 deletions(-)
diff --git a/Problem1/Problem1.cpp b/Problem1/Problem1.cpp
@@ -10,25 +10,54 @@
#include <vector>
#include <sstream>
#include <string>
+#include <chrono>
+#include <algorithm>
using namespace std;
// Function prototypes
vector<int> bucketSort(vector<int> unsortedVector);
-vector<int> insertSort(vector<int> unsortedVector);
+vector<int> insertionSort(vector<int> unsortedVector);
string vectorToString(vector<int> vector);
int findMax(vector<int> v);
-
+vector<int> generateRandomVector(int low, int high, int size);
+void showProgressBar(int width, double progress);
int main()
{
- vector<int> unsorted = { 41, 12, 12, 53, 14, 5, 62, 7, 12, 28, 9 };
- vector<int> sorted = bucketSort(unsorted);
- vector<int> insertSorted = insertSort(unsorted);
- cout << "The unsorted vector: " << vectorToString(unsorted) << endl;
- cout << "The sorted vector: " << vectorToString(sorted) << endl;
- cout << "The sorted vector using InsertSort: " << vectorToString(insertSorted) << endl;
+ int iterations = 100;
+
+ srand(12345);
+
+ vector<double> durations(iterations);
+
+ for (int i = 0; i < iterations; i++) {
+
+ showProgressBar(100, (double)i / iterations);
+
+ vector<int> unsorted = generateRandomVector(0, 999999, 100000);
+
+ auto start = chrono::high_resolution_clock::now();
+
+ vector<int> sorted = bucketSort(unsorted);
+
+ auto end = chrono::high_resolution_clock::now();
+
+ chrono::duration<double> elapsed = end - start;
+
+ durations[i] = elapsed.count();
+ }
+
+ //find highest duration
+ auto highest = max_element(durations.begin(), durations.end());
+
+ cout << "\nThe highest duration was: " << *highest << endl;
+
+ //vector<int> insertSorted = insertionSort(unsorted);
+ //cout << "The unsorted vector: " << vectorToString(unsorted) << endl;
+ //cout << "The sorted vector: " << vectorToString(sorted) << endl;
+ //cout << "The sorted vector using InsertSort: " << vectorToString(insertSorted) << endl;
return 0;
}
@@ -40,15 +69,15 @@ int main()
* @param v: the unsorted vector
* @return: the sorted vector
*/
-vector<int> bucketSort(vector<int> v)
+vector<int> bucketSort(vector<int> v)
{
int max = findMax(v);
// Create buckets (each bucket is a vector)
vector<vector<int>> w(max + 1, vector<int>());
-
+
// Add values to buckets
- for (int i = 0; i < (int) v.size(); i++)
+ for (int i = 0; i < (int)v.size(); i++)
{
w[v[i]].push_back(v[i]);
}
@@ -57,7 +86,7 @@ vector<int> bucketSort(vector<int> v)
vector<int> sorted(0);
// Append from buckets in order to sorted vector
- for (int i = 0; i < (int) w.size(); i++)
+ for (int i = 0; i < (int)w.size(); i++)
{
//check if bucket is empty
if (!w[i].empty())
@@ -78,14 +107,14 @@ vector<int> bucketSort(vector<int> v)
* @param v: the unsorted vector
* @return: the sorted vector
*/
-vector<int> insertSort(vector<int> v)
+vector<int> insertionSort(vector<int> v)
{
int i, j, key;
- for (i = 0; i < v.size(); i++)
+ for (i = 0; i < v.size(); i++)
{
key = v[i];
j = i - 1;
-
+
while (j >= 0 && v[j] > key)
{
v[j + 1] = v[j];
@@ -105,7 +134,7 @@ vector<int> insertSort(vector<int> v)
int findMax(vector<int> v)
{
int max = v[0];
- for (int i = 1; i < (int) v.size(); i++)
+ for (int i = 1; i < (int)v.size(); i++)
{
if (v[i] > max)
{
@@ -126,7 +155,7 @@ int findMax(vector<int> v)
string vectorToString(vector<int> vector)
{
string output = "{";
- for (int i = 0; i < (int) vector.size(); i++)
+ for (int i = 0; i < (int)vector.size(); i++)
{
output += to_string(vector[i]);
if (i != vector.size() - 1)
@@ -138,3 +167,41 @@ string vectorToString(vector<int> vector)
return output;
}
+
+
+/*
+* Function: generateRandomVector
+* Generate a random vector of a given size
+* @param low: the lowest possible value in the vector
+* @param high: the highest possible value in the vector
+* @param size: the size of the vector to generate
+*/
+vector<int> generateRandomVector(int low, int high, int size)
+{
+ vector<int> v(size);
+ for (int i = 0; i < size; i++)
+ {
+ v[i] = rand() % (high - low + 1) + low;
+ }
+
+ return v;
+}
+
+/*
+* Function: showProgressBar
+* Show a progress bar in the console
+* @param width: the width of the progress bar
+* @param progress: the progress of the bar
+*/
+void showProgressBar(int width, double progress) {
+ int pos = width * progress;
+
+ cout << "[";
+ for (int i = 0; i < width; ++i) {
+ if (i < pos) cout << "=";
+ else if (i == pos) cout << ">";
+ else cout << " ";
+ }
+ cout << "] " << int(progress * 100.0) << " %\r";
+ cout.flush(); // Important to flush the output
+}
+\ No newline at end of file
