From 9e38cd273d422e5eb7def2a51065960020717d81 Mon Sep 17 00:00:00 2001
From: Angel Dimitriev <achi_d@abv.bg>
Date: Wed, 22 Dec 2021 19:01:57 +0200
Subject: Create SelectionSort.cpp

---
 Sem. 11/SelectionSort.cpp | 85 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 85 insertions(+)
 create mode 100644 Sem. 11/SelectionSort.cpp

(limited to 'Sem. 11/SelectionSort.cpp')

diff --git a/Sem. 11/SelectionSort.cpp b/Sem. 11/SelectionSort.cpp
new file mode 100644
index 0000000..053ff0a
--- /dev/null
+++ b/Sem. 11/SelectionSort.cpp	
@@ -0,0 +1,85 @@
+#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;
+	}
+}
+
+
+
+// Инверсия:  i < j arr[i] > arr[j]
+// Масив е сортиран, когато в него няма инверсии.
+
+//bubbleSort на една стъпка чупи една инверсия.
+
+// В масив средно колко инверсии?
+
+//Колко най-много инверсии може да имаме ? binom(n,2) = n * (n-1)/ 2
+
+// Каква е вероятността два конкретни елемента да са в инвесия.
+
+// Сортираме числата {1...n}
+
+// Вероятност <i,j> да са в инвесия = всички перм. на {1...n}, в които i е в инверсия в j  n!/2
+								     /всички пермутации       = n!
+
+// Вероятност два индекса да са в инверсия: 1 / 2
+
+
+//Средно колко инверсии имаме в масив: Възможности за инверсия * вероятност да се случи тази инверсия
+//                                      n * (n - 1) / 2        *  1/2 = 
+
+// Среден брой инверсии: n * (n-1)/ 4
+// Бъбъл сорт на една стъпка чупи най-много една инвесия.
+// => средните стъпки на бъбълсорт >= n * (n-1)/ 4  =  О(n^2)
+
+
+[][][][][][][][]
+
+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] << " ";
+}
-- 
cgit v1.3.1-23-gd82d


From 598f0b3df2ff3b94d65d38db750906d3cd76ff1e Mon Sep 17 00:00:00 2001
From: Angel Dimitriev <achi_d@abv.bg>
Date: Wed, 22 Dec 2021 19:02:15 +0200
Subject: Update SelectionSort.cpp

---
 Sem. 11/SelectionSort.cpp | 51 -----------------------------------------------
 1 file changed, 51 deletions(-)

(limited to 'Sem. 11/SelectionSort.cpp')

diff --git a/Sem. 11/SelectionSort.cpp b/Sem. 11/SelectionSort.cpp
index 053ff0a..87cc6eb 100644
--- a/Sem. 11/SelectionSort.cpp	
+++ b/Sem. 11/SelectionSort.cpp	
@@ -1,63 +1,12 @@
 #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;
-	}
-}
-
-
-
-// Инверсия:  i < j arr[i] > arr[j]
-// Масив е сортиран, когато в него няма инверсии.
-
-//bubbleSort на една стъпка чупи една инверсия.
-
-// В масив средно колко инверсии?
-
-//Колко най-много инверсии може да имаме ? binom(n,2) = n * (n-1)/ 2
-
-// Каква е вероятността два конкретни елемента да са в инвесия.
-
-// Сортираме числата {1...n}
-
-// Вероятност <i,j> да са в инвесия = всички перм. на {1...n}, в които i е в инверсия в j  n!/2
-								     /всички пермутации       = n!
-
-// Вероятност два индекса да са в инверсия: 1 / 2
-
-
-//Средно колко инверсии имаме в масив: Възможности за инверсия * вероятност да се случи тази инверсия
-//                                      n * (n - 1) / 2        *  1/2 = 
-
-// Среден брой инверсии: n * (n-1)/ 4
-// Бъбъл сорт на една стъпка чупи най-много една инвесия.
-// => средните стъпки на бъбълсорт >= n * (n-1)/ 4  =  О(n^2)
-
-
-[][][][][][][][]
 
 void selectionSort(int* arr, unsigned size)
 {
-- 
cgit v1.3.1-23-gd82d