From 9e38cd273d422e5eb7def2a51065960020717d81 Mon Sep 17 00:00:00 2001 From: Angel Dimitriev 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') 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 +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} + +// Вероятност да са в инвесия = всички перм. на {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 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') 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 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} - -// Вероятност да са в инвесия = всички перм. на {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 From f44b351868261219d95f634bca33230e7a6f6d03 Mon Sep 17 00:00:00 2001 From: Angel Dimitriev Date: Wed, 22 Dec 2021 19:03:16 +0200 Subject: Create BubbleSort.cpp --- Sem. 11/BubbleSort.cpp | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 Sem. 11/BubbleSort.cpp (limited to 'Sem. 11') 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 +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] << " "; +} -- cgit v1.3.1-23-gd82d From f45802125a7cd05d10a17368e015111281863af9 Mon Sep 17 00:00:00 2001 From: Angel Dimitriev Date: Wed, 22 Dec 2021 19:05:47 +0200 Subject: Create README.md --- Sem. 11/README.md | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) create mode 100644 Sem. 11/README.md (limited to 'Sem. 11') diff --git a/Sem. 11/README.md b/Sem. 11/README.md new file mode 100644 index 0000000..f46c895 --- /dev/null +++ b/Sem. 11/README.md @@ -0,0 +1,18 @@ + + +# Анализ на алгоритми. Алгоритми за търсене и сортиране. + +#### Алгоритми за търсене. + + - Linear search + - Binary search +#### Алгоритми за сортиране. + - Bubble sort + - Selection sort + + + + +

Задачи

+ +**Задача 1:** -- cgit v1.3.1-23-gd82d From 9002b71f11507389e83248517a10e7851d44f075 Mon Sep 17 00:00:00 2001 From: Angel Dimitriev Date: Wed, 22 Dec 2021 19:06:32 +0200 Subject: Create binarySearch.cpp --- Sem. 11/binarySearch.cpp | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) create mode 100644 Sem. 11/binarySearch.cpp (limited to 'Sem. 11') 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 +#include +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); +} -- cgit v1.3.1-23-gd82d From 745733dd452b7632a1968b97603b83a868b71854 Mon Sep 17 00:00:00 2001 From: Angel Dimitriev Date: Wed, 22 Dec 2021 19:06:42 +0200 Subject: Rename binarySearch.cpp to BinarySearch.cpp --- Sem. 11/BinarySearch.cpp | 44 ++++++++++++++++++++++++++++++++++++++++++++ Sem. 11/binarySearch.cpp | 44 -------------------------------------------- 2 files changed, 44 insertions(+), 44 deletions(-) create mode 100644 Sem. 11/BinarySearch.cpp delete mode 100644 Sem. 11/binarySearch.cpp (limited to 'Sem. 11') 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 +#include +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/binarySearch.cpp b/Sem. 11/binarySearch.cpp deleted file mode 100644 index df678ce..0000000 --- a/Sem. 11/binarySearch.cpp +++ /dev/null @@ -1,44 +0,0 @@ -#include -#include -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); -} -- cgit v1.3.1-23-gd82d From a4a29efa276a13233489f1445c01652024a247ce Mon Sep 17 00:00:00 2001 From: Angel Dimitriev Date: Wed, 22 Dec 2021 19:07:07 +0200 Subject: Create LinearSearch.cpp --- Sem. 11/LinearSearch.cpp | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) create mode 100644 Sem. 11/LinearSearch.cpp (limited to 'Sem. 11') 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 +#include +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); +} + -- cgit v1.3.1-23-gd82d From 9579ce0302f18663bb0bd34d3f659636183852f5 Mon Sep 17 00:00:00 2001 From: Angel Dimitriev Date: Wed, 22 Dec 2021 19:16:59 +0200 Subject: Update README.md --- Sem. 11/README.md | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'Sem. 11') diff --git a/Sem. 11/README.md b/Sem. 11/README.md index f46c895..df52ca9 100644 --- a/Sem. 11/README.md +++ b/Sem. 11/README.md @@ -1,6 +1,20 @@ # Анализ на алгоритми. Алгоритми за търсене и сортиране. +Сложност: Функция по големината на входа (N) + +**Пример**: + + - При търсене в масив - големината на входа е големината на масива + - При проверка число дали е просто - големината на входа е числото. + +При анализа на алгоритми НЕ се интересуваме от точната функция! +Интересуваме се само то асимптотиката на функцията. +Колко бързо расте функцията при n->безкрайност. + +![enter image description here](https://i.ibb.co/TP0Xrz4/ff.png) +Тук релциите за по-малко и по-равно не са тези, които познаваме. +Тук визираме скоростта на растежа на функцията. #### Алгоритми за търсене. -- cgit v1.3.1-23-gd82d From 789688fb010a6b2575229df12ec4566996a859cd Mon Sep 17 00:00:00 2001 From: Angel Dimitriev Date: Wed, 22 Dec 2021 19:19:44 +0200 Subject: Update README.md --- Sem. 11/README.md | 1 + 1 file changed, 1 insertion(+) (limited to 'Sem. 11') diff --git a/Sem. 11/README.md b/Sem. 11/README.md index df52ca9..8f6d197 100644 --- a/Sem. 11/README.md +++ b/Sem. 11/README.md @@ -13,6 +13,7 @@ Колко бързо расте функцията при n->безкрайност. ![enter image description here](https://i.ibb.co/TP0Xrz4/ff.png) + Тук релциите за по-малко и по-равно не са тези, които познаваме. Тук визираме скоростта на растежа на функцията. -- cgit v1.3.1-23-gd82d