Merge branch 'main' of https://github.com/Angeld55/Introduction_to_programming_FMI

5 files changed, 195 insertions, 0 deletions

diff --git a/Sem. 11/BinarySearch.cpp b/Sem. 11/BinarySearch.cpp
new file mode 100644
index 0000000..df678ce
--- /dev/null
+++ b/Sem. 11/BinarySearch.cpp
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <vector>
+using namespace std;
+
+
+bool linearSearch(const int arr[], unsigned size, int el)
+{
+	for (unsigned i = 0; i < size; i++)
+	{
+		if (arr[i] == el)
+			return true;
+	}
+	return false;
+}
+
+bool binarySearch(const int* arr, unsigned size, int searched)
+{
+	unsigned fromIndex = 0;
+	unsigned toIndex = size - 1;
+
+	while (fromIndex <= toIndex)
+	{
+		unsigned midIndex = fromIndex + (toIndex - fromIndex) / 2;
+
+		if (arr[midIndex] == searched)
+			return true;
+
+		if (arr[midIndex] < searched)
+			fromIndex = midIndex + 1;
+		else
+			toIndex = midIndex - 1;
+	}
+
+	return false;
+}
+
+
+
+int main()
+{
+	const unsigned SIZE = 8;
+	int arr[]  { 1, 12, 33, 14,35,4,17,38};
+	cout << linearSearch(arr, SIZE, 14);
+}
diff --git a/Sem. 11/BubbleSort.cpp b/Sem. 11/BubbleSort.cpp
new file mode 100644
index 0000000..217bf32
--- /dev/null
+++ b/Sem. 11/BubbleSort.cpp
@@ -0,0 +1,39 @@
+#include <iostream>
+using namespace std;
+
+
+void swap(int& a, int& b)
+{
+	int temp = a;
+	a = b;
+	b = temp;
+}
+
+void bubbleSort(int* arr, unsigned size)
+{
+	for (unsigned j = 0; j < size - 1; j++)
+	{
+		bool isSwapped = false;
+
+		for (unsigned i = 0; i < size - 1 - j; i++)
+		{
+			if (arr[i] > arr[i + 1])
+			{
+				swap(arr[i], arr[i + 1]);
+				isSwapped = true;
+			}
+		}
+
+		if (!isSwapped)
+			return;
+	}
+}
+
+int main()
+{
+	int arr[] = { 1,2,2,1, 1 };
+	selectionSort(arr, 5);
+
+	for (int i = 0; i < 5; i++)
+		cout << arr[i] << " ";
+}
diff --git a/Sem. 11/LinearSearch.cpp b/Sem. 11/LinearSearch.cpp
new file mode 100644
index 0000000..b0446e1
--- /dev/null
+++ b/Sem. 11/LinearSearch.cpp
@@ -0,0 +1,45 @@
+#include <iostream>
+#include <vector>
+using namespace std;
+
+
+bool linearSearch(const int arr[], unsigned size, int el)
+{
+	for (unsigned i = 0; i < size; i++)
+	{
+		if (arr[i] == el)
+			return true;
+	}
+	return false;
+}
+
+bool binarySearch(const int arr[], unsigned size, int searched)
+{
+	unsigned fromIndex = 0;
+	unsigned toIndex = size - 1;
+
+	while (fromIndex <= toIndex)
+	{
+		unsigned midIndex = fromIndex + (toIndex - fromIndex) / 2;
+
+		if (arr[midIndex] == searched)
+			return true;
+
+		if (arr[midIndex] < searched)
+			fromIndex = midIndex + 1;
+		else
+			toIndex = midIndex - 1;
+	}
+
+	return false;
+}
+
+
+
+int main()
+{
+	const unsigned SIZE = 8;
+	int arr[]  { 1, 12, 33, 14,35,4,17,38};
+	cout << linearSearch(arr, SIZE, 14);
+}
+
diff --git a/Sem. 11/README.md b/Sem. 11/README.md
new file mode 100644
index 0000000..8f6d197
--- /dev/null
+++ b/Sem. 11/README.md
@@ -0,0 +1,33 @@
+
+
+# Анализ на алгоритми. Алгоритми за търсене и сортиране.
+Сложност: Функция по големината на входа (N)
+
+**Пример**: 
+
+ - При търсене в масив - големината на входа е големината на масива
+ -  При проверка число дали е просто - големината на входа е числото.
+
+При анализа на алгоритми НЕ се интересуваме от точната функция!
+Интересуваме се само то асимптотиката на функцията.
+Колко бързо расте функцията при n->безкрайност.
+
+![enter image description here](https://i.ibb.co/TP0Xrz4/ff.png)
+
+Тук релциите за по-малко и по-равно не са тези, които познаваме.
+Тук визираме скоростта на растежа на функцията.
+
+#### Алгоритми за търсене.
+
+ - Linear search
+ - Binary search
+#### Алгоритми за сортиране.
+ - Bubble sort
+ - Selection sort
+
+
+
+
+<h3>Задачи</h3>
+
+**Задача 1:**
diff --git a/Sem. 11/SelectionSort.cpp b/Sem. 11/SelectionSort.cpp
new file mode 100644
index 0000000..87cc6eb
--- /dev/null
+++ b/Sem. 11/SelectionSort.cpp
@@ -0,0 +1,34 @@
+#include <iostream>
+using namespace std;
+
+void swap(int& a, int& b)
+{
+	int temp = a;
+	a = b;
+	b = temp;
+}
+
+void selectionSort(int* arr, unsigned size)
+{
+	for (unsigned i = 0; i < size - 1; i++)
+	{
+		//findMin
+		int minElementIndex = i;
+		for (unsigned j = i + 1; j < size; j++)
+		{
+			if (arr[j] < arr[minElementIndex])
+				minElementIndex = j;
+		}
+		if (minElementIndex != i)
+			swap(arr[i], arr[minElementIndex]);
+	}
+}
+
+int main()
+{
+	int arr[] = { 1,2,2,1, 1 };
+	selectionSort(arr, 5);
+
+	for (int i = 0; i < 5; i++)
+		cout << arr[i] << " ";
+}