Add Sem02

3 files changed, 206 insertions, 0 deletions

diff --git a/Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp b/Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp
new file mode 100644
index 0000000..b5b2b1c
--- /dev/null
+++ b/Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp
@@ -0,0 +1,54 @@
+#include <iostream>
+
+template<typename T>
+void merge(T* arr1, unsigned len1, 
+           T* arr2, unsigned len2)
+{
+	T* resultArray = new T[len1 + len2];
+
+	unsigned cursor1 = 0;
+	unsigned cursor2 = 0;
+	unsigned resultCursor = 0;
+
+	while (cursor1 < len1 && cursor2 < len2)
+	{
+		if (arr1[cursor1] <= arr2[cursor2])
+			resultArray[resultCursor++] = arr1[cursor1++];
+		else
+			resultArray[resultCursor++] = arr2[cursor2++];
+	}
+
+	while (cursor1 < len1)
+		resultArray[resultCursor++] = arr1[cursor1++];
+    
+	while (cursor2 < len2)
+		resultArray[resultCursor++] = arr2[cursor2++];
+
+	for (size_t i = 0; i < len1 + len2; i++)
+		arr1[i] = resultArray[i];
+    
+	delete[] resultArray;
+}
+
+template <typename T>
+void mergeSort(T* arr, unsigned len)
+{
+	if (len < 2)
+		return;
+
+	unsigned mid = len / 2;
+
+	mergeSort(arr, mid);
+	mergeSort(arr + mid, len - mid);
+
+	merge<T>(arr, mid, arr + mid, len - mid);
+}
+
+int main()
+{
+	int arr[4] = { 9, 6, 5, 8 };
+	mergeSort(arr, 4);
+
+	for (int i = 0; i < 4; i++)
+		std::cout << arr[i] << " ";
+}
\ No newline at end of file
diff --git a/Seminar02/src/sorting-algorithms/merge-sort.cpp b/Seminar02/src/sorting-algorithms/merge-sort.cpp
new file mode 100644
index 0000000..3ae3c09
--- /dev/null
+++ b/Seminar02/src/sorting-algorithms/merge-sort.cpp
@@ -0,0 +1,87 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+template<class T>
+void merge(T* firstArray, unsigned firstSize, 
+           T* secondArray, unsigned secondSize,
+           T* buffer)
+{
+    unsigned firstIter = 0;
+    unsigned secondIter = 0;
+    unsigned resultIter = 0;
+
+    while(firstIter < firstSize && secondIter < secondSize)
+    {
+        if(firstArray[firstIter] > secondArray[secondIter])
+        {
+            buffer[resultIter] = secondArray[secondIter];
+            secondIter++;
+        }
+        else
+        {
+            buffer[resultIter] = firstArray[firstIter];
+            firstIter++;
+        }
+        resultIter++;
+    }
+
+    while(firstIter < firstSize)
+    {
+        buffer[resultIter++] = firstArray[firstIter++];
+    }
+
+    while(secondIter < secondSize)
+    {
+        buffer[resultIter++] = secondArray[secondIter++];
+    }
+
+    for (size_t i = 0; i < firstSize + secondSize; i++)
+    {
+        firstArray[i] = buffer[i];
+    }
+}
+
+
+template<class T>
+void mergeSortStep(T* arr, unsigned size, T* buffer)
+{
+    if(size < 2)
+        return;
+    
+    unsigned mid = size / 2;
+    mergeSortStep(arr, mid, buffer);
+    mergeSortStep(arr + mid, size - mid, buffer);
+
+    merge(arr, mid, arr + mid, size - mid, buffer);
+
+    for (size_t i = 0; i < size; i++)
+        arr[i] = buffer[i];
+}
+
+template<class T>
+void mergeSort(T* arr, unsigned size)
+{
+    if(size < 2)
+        return;
+    
+    T* buffer = new T[size];
+    mergeSortStep(arr, size, buffer);
+    delete[] buffer;
+}
+
+int main()
+{
+    std::vector<int> numbers;
+    unsigned size = rand() % 10000;
+    numbers.resize(size);
+
+    for (size_t i = 0; i < size; i++)
+    {
+        numbers[i] = rand() % 10000;
+    }
+
+    mergeSort(numbers.data(), numbers.size());
+
+    std::cout << std::is_sorted(numbers.begin(), numbers.end()) << std::endl;
+}
\ No newline at end of file
diff --git a/Seminar02/src/sorting-algorithms/quick-sort.cpp b/Seminar02/src/sorting-algorithms/quick-sort.cpp
new file mode 100644
index 0000000..3069738
--- /dev/null
+++ b/Seminar02/src/sorting-algorithms/quick-sort.cpp
@@ -0,0 +1,65 @@
+#include <iostream>
+#include <algorithm> // std::is_sorted
+#include <vector>    // std::vector
+
+/// @brief Reorders the elements in such a way that all elements for which are less than pivot 
+// precede all elements which are greater or equal to pivot. Relative order of the elements is not preserved.
+// TODO: remove copy somehow???
+template <class T>
+size_t partition(T* pArr, size_t len)
+{
+    if (pArr[0] > pArr[len - 1])
+        std::swap(pArr[0], pArr[len - 1]);
+
+    T& partitioningElement = pArr[len - 1];
+    size_t left = 0;
+    size_t right = len - 1;
+
+    while (true)
+    {
+        while (pArr[++left] < partitioningElement)
+            ;
+
+        while (pArr[--right] > partitioningElement)
+        {
+            if (left == right)
+                break;
+        }
+
+        if (left >= right)
+            break;
+
+        std::swap(pArr[left], pArr[right]);
+    }
+
+    std::swap(pArr[left], partitioningElement);
+    return left;
+}
+
+template<class T>
+void quickSort(T* arr, unsigned size)
+{
+    if(size < 2)
+        return;
+    
+    unsigned pivotPos = partition(arr, size);
+
+    quickSort(arr, pivotPos);
+    quickSort(arr + pivotPos + 1, size - pivotPos - 1);
+}
+
+int main()
+{
+    std::vector<int> numbers;
+    unsigned size = rand() % 10000;
+    numbers.resize(size);
+
+    for (size_t i = 0; i < size; i++)
+    {
+        numbers[i] = rand() % 10000;
+    }
+
+    quickSort(numbers.data(), numbers.size());
+
+    std::cout << std::is_sorted(numbers.begin(), numbers.end());
+}
\ No newline at end of file