DSA-Assignments

commit 014a161645610766815b88c79cf1b2705d4bab40
parent d327c1affd661599a8ef03ec7b6a4ebcff16de96
Author: William Lindholm <a22willi@student.his.se>
Date:   Thu, 16 Nov 2023 14:51:40 +0100

Implemented modified version of bucket sort.

Diffstat:
M
Problem1/Problem1.cpp
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 46 insertions(+), 0 deletions(-)
diff --git a/Problem1/Problem1.cpp b/Problem1/Problem1.cpp
@@ -8,12 +8,14 @@
 #include <iostream>
 #include <vector>
 #include <sstream>
+#include <string>
 
 using namespace std;
 
 // Function prototypes
 vector<int> bucketSort(vector<int> unsortedVector);
 string vectorToString(vector<int> vector);
+int findMax(vector<int> v);
 
 int main()
 {
@@ -35,7 +37,51 @@ int main()
  */
 vector<int> bucketSort(vector<int> v) 
 {
+	int max = findMax(v);
+
+	// Create buckets
+	vector<int> w(max + 1);
 	
+	// Add values to buckets
+	for (int i = 0; i < v.size(); i++)
+	{
+		w[v[i]] = v[i];
+	}
+
+	// Create sorted vector
+	vector<int> sorted(0);
+
+	// Append from buckets in order to sorted vector
+	for (int i = 0; i < w.size(); i++)
+	{
+		
+		if (w[i] != NULL || w[i] != 0)
+		{
+			sorted.push_back(w[i]);
+		}
+	}
+
+	return sorted;
+}
+
+/*
+ * Function: findMax
+ * Find the maximum value in a vector
+ * @param v: the vector to search
+ * @return: the maximum value in the vector
+ */
+int findMax(vector<int> v)
+{
+	int max = v[0];
+	for (int i = 1; i < v.size(); i++)
+	{
+		if (v[i] > max)
+		{
+			max = v[i];
+		}
+	}
+
+	return max;
 }