DSA-Assignments

commit 516807e594d6d1bcbca96dd02e270cfa26c23cee
parent ac4f3fc710a5cbbde37bf4d5587bf123b3d3f1c9
Author: Victor Adamson <a20vicad@student.his.se>
Date:   Mon, 27 Nov 2023 16:14:26 +0100

Implemented Insert sort

Diffstat:
M
Problem1/Problem1.cpp
 | 
21
+++++++++++++++++++--

1 file changed, 19 insertions(+), 2 deletions(-)
diff --git a/Problem1/Problem1.cpp b/Problem1/Problem1.cpp
@@ -16,6 +16,7 @@ using namespace std;
 
 // Function prototypes
 vector<int> bucketSort(vector<int> unsortedVector);
+vector<int> insertSort(vector<int> unsortedVector);
 string vectorToString(vector<int> vector);
 int findMax(vector<int> v);
 
@@ -24,9 +25,10 @@ int main()
 {
 	vector<int> unsorted = { 41, 12, 12, 53, 14, 5, 62, 7, 12, 28, 9 };
 	vector<int> sorted = bucketSort(unsorted);
-
+	vector<int> funny = insertSort(unsorted);
 	cout << "The unsorted vector: " << vectorToString(unsorted) << endl;
 	cout << "The sorted vector: " << vectorToString(sorted) << endl;
+	cout << "The sorted vector using InsertSort: " << vectorToString(funny) << endl;
 
 	return 0;
 }
@@ -68,13 +70,28 @@ vector<int> bucketSort(vector<int> v)
 	return sorted;
 }
 
+/*
+ * Function: insertSort
+ * Sort an unsorted vector using insertionsort
+ * @param v: the unsorted vector
+ * @return: the sorted vector
+ */
 vector<int> insertSort(vector<int> v) 
 {
-	int i, j, temp;
+	int i, j, key;
 	for (i = 0; i < v.size(); i++) 
 	{
+		key = v[i];
+		j = i - 1;
 		
+		while (j >= 0 && v[j] > key)
+		{
+			v[j + 1] = v[j];
+			j = j - 1;
+		}
+		v[j + 1] = key;
 	}
+	return v;
 }
 
 /*