[SDP/S07] Added sorting algorithm implementations

1 files changed, 154 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/07-Seminar-23.11.2022.cpp b/Year 2/Structures and data algorithms/07-Seminar-23.11.2022.cpp
new file mode 100644
index 0000000..5ce658e
--- /dev/null
+++ b/Year 2/Structures and data algorithms/07-Seminar-23.11.2022.cpp
@@ -0,0 +1,154 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+// Bubble sort
+
+template <class T>
+void manualSwap(std::vector<T>& v, int s1, int s2) {
+	T temp = v[s1];
+	v[s1] = v[s2];
+	v[s2] = temp;
+}
+
+template <class T>
+void bubbleSort(std::vector<T>& v) {
+	for (int i = 0; i < v.size(); i++) {
+		for (int j = i + 1; j < v.size(); j++) {
+			if (v[i] > v[j])
+				manualSwap(v, i, j);
+		}
+	}
+}
+
+// Insertion sort
+
+template <class T>
+void insertionSort(std::vector<T>& v) {
+	for (int i = 1; i < v.size(); i++) {
+		for (int j = i; j > 0 && v[j - 1] > v[j]; j--)
+			std::swap(v[j], v[j-1]);
+	}
+}
+
+// Selection sort
+
+template <class T>
+void selectionSort(std::vector<T>& v) {
+	for (int i = 0, min = 0; i < v.size() - 1; i++, min = i) {
+		for (int j = i + 1; j < v.size(); j++) {
+			if (v[j] < v[min]) min = j;
+		}
+		if (i != min) std::swap(v[i], v[min]);
+	}
+}
+
+// Merge sort
+
+template <class T>
+void merge(std::vector<T>& v, int start1, int size1, int start2, int size2) {
+	std::vector<T> temp(size1 + size2);
+	for (int t = 0, i = 0, j = 0; t < temp.size(); t++) {
+		if (j >= size2 || (i < size1 && v[start1 + i] < v[start2 + j]))
+			temp[t] = v[start1 + i++];
+		else
+			temp[t] = v[start2 + j++];
+	}
+
+	for (int i = 0; i < temp.size(); i++)
+		v[start1 + i] = temp[i];
+}
+
+template <class T>
+void mergeSort(std::vector<T>& v, int start = 0, int size = -1) {
+	if (size == -1) size = v.size();
+	if (size < 2) return;
+
+	int mid = size / 2;
+	mergeSort(v, start, mid);
+	mergeSort(v, start + mid, size - mid);
+	merge(v, start, mid, start + mid, size - mid);
+}
+
+// Quick sort
+
+template <class T>
+void quickSort(std::vector<T>& v, int start = 0, int pivot = -1) {
+	if (pivot == -1) pivot = v.size() - 1;
+	if (pivot <= start) return;
+
+	int end = pivot;
+	for (int i = start; i < pivot; i++) {
+		if (v[i] > v[pivot]) {
+			if (pivot - i > 1) // if pivot and i aren't next to each other, make space for i on the right of pivot
+				std::swap(v[pivot-1], v[pivot]);
+			std::swap(v[i], v[pivot]);
+			i--;
+			pivot--;
+		}
+	}
+	quickSort(v, start, pivot - 1);
+	quickSort(v, pivot + 1, end);
+}
+
+// Count sort
+
+void countSort(std::vector<unsigned>& v) {
+	unsigned max = 0;
+	for (auto num : v) {
+		if (num > max) max = num;
+	}
+	std::vector<int> counts(max + 1);
+
+	for (auto num : v) {
+		counts[num]++;
+	}
+
+	int prev = 0;
+	for (int i = 0; i < counts.size(); i++) {
+		counts[i] += prev;
+		prev = counts[i];
+	}
+
+	for (int i = 0; i < v.size(); i++) {
+		if (counts[v[i]] - 1 > i) {
+			std::swap(v[i], v[--counts[v[i]]]);
+			i--;
+		}
+	}
+}
+
+// main
+
+template <class T>
+std::ostream& operator<<(std::ostream& ostr, std::vector<T> vec) {
+	for (auto elem : vec)
+		ostr << elem << ", ";
+	return ostr;
+}
+
+int main() {
+	std::vector<int> vec1 = { 39, 27, 43, 3, 9, 82, 10 };
+	bubbleSort(vec1);
+	std::cout << "Bubble:    " << vec1 << std::endl;
+
+	std::vector<int> vec2 = { 39, 27, 43, 3, 9, 82, 10 };
+	insertionSort(vec2);
+	std::cout << "Insertion: " << vec2 << std::endl;
+
+	std::vector<int> vec3 = { 39, 27, 43, 3, 9, 82, 10 };
+	selectionSort(vec3);
+	std::cout << "Selection: " << vec3 << std::endl;
+
+	std::vector<int> vec4 = { 39, 27, 43, 3, 9, 82, 10 };
+	mergeSort(vec4);
+	std::cout << "Merge:     " << vec4 << std::endl;
+
+	std::vector<int> vec5 = { 39, 27, 43, 3, 9, 82, 10 };
+	quickSort(vec5);
+	std::cout << "Quick:     " << vec5 << std::endl;
+
+	std::vector<unsigned> vec6 = { 39, 27, 43, 3, 9, 82, 10 };
+	countSort(vec6);
+	std::cout << "Count:     " << vec6 << std::endl;
+}