Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar02
diff options
context:
space:
mode:
Commitdf74c873bc11ad90fb26e582c7be0ed092228661 (patch)
Author
 Stoycho Kyosev <skyosev@2a01-5a8-317-bbdc-4f2b-da5-db2e-fb02.v6.vivacom.bg>
2024-10-25 18:04:36 -0400
Committer
 Stoycho Kyosev <skyosev@2a01-5a8-317-bbdc-4f2b-da5-db2e-fb02.v6.vivacom.bg>
2024-10-25 18:04:36 -0400
Files73d2662eeddf5ebddfa6982270edd21fb4588de9 /Seminar02
Data-structures-and-algorithms-df74c873bc11ad90fb26e582c7be0ed092228661.tar
Data-structures-and-algorithms-df74c873bc11ad90fb26e582c7be0ed092228661.tar.gz
Data-structures-and-algorithms-df74c873bc11ad90fb26e582c7be0ed092228661.zip
Parentc31c7c53f87104c254aac5ba99e984f9ec373d9a (diff)
Add sem03
2 files changed, 19 insertions, 5 deletions
-rw-r--r--Seminar02/README.md17
-rw-r--r--Seminar02/src/sorting-algorithms/quick-sort.cpp7
diff --git a/Seminar02/README.md b/Seminar02/README.md
index 9399aea..64f3a96 100644
--- a/Seminar02/README.md
+++ b/Seminar02/README.md
@@ -122,4 +122,19 @@ in-place - Не
Сложност по памет - Θ(n)
-## Алгоритъмът Quick Sort \ No newline at end of file
+## Алгоритъмът Quicksort
+Нека предположим, че избираме произволен елемент от `p` от `n` елементи, които искаме да сортираме. `Quicksort` разделя останалите `n - 1` елемента на две групи - тези, които са по - малки от `p` и тези, които са по - големи. Всеки от по - малките елементи се намира вляво от всеки от по - големите.
+
+Подобно разделяне ни носи две неща:
+
+* Избраният елемент `p` остава на точната позиция на която ще бъде в сортирания масив.
+* След това разбиване никой елемент не се премества от лявата част в дясната. Това означава, че можем да разглеждаме двете части като отделни масиви!
+
+Функцията, която използваме за да направи такова разделение, наричаме `partition`. След като изберем елемент (наричан `pivot`) извикваме `partition` върху масива и след като тя приключи рекурсивно извикваме `Quicksort` върху лявата подмасива на по - малките елементи и този на по - големите.
+
+* Worst case complextiy = O(n^2) - Можем винаги да избираме най - големия или най - малкия. Тогава няма да имаме два подмасива а един с големина `n - 1`.
+* Average case = O(nlog(n)) - Добре е тук да обърнем внимание на средния случай като той ни дава много по - добра представа за реалния потенциал на `Quicksort`. Въпрки, че в най - лошия случай това е квадратичен алгоритъм, очакваме че няма да вземем най - големия, нито най - малкия, а елемент близък до средния по големина.
+* Стабилен - не, `partition` не гарантира, че ще запази първоначалната наредба на елементите.
+* in place - да
+
+## std::partition, std::merge \ No newline at end of file
diff --git a/Seminar02/src/sorting-algorithms/quick-sort.cpp b/Seminar02/src/sorting-algorithms/quick-sort.cpp
index 3069738..f82e8c5 100644
--- a/Seminar02/src/sorting-algorithms/quick-sort.cpp
+++ b/Seminar02/src/sorting-algorithms/quick-sort.cpp
@@ -4,7 +4,6 @@
/// @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)
{
@@ -37,12 +36,12 @@ size_t partition(T* pArr, size_t len)
}
template<class T>
-void quickSort(T* arr, unsigned size)
+void quickSort(T* arr, size_t size)
{
if(size < 2)
return;
- unsigned pivotPos = partition(arr, size);
+ size_t pivotPos = partition(arr, size);
quickSort(arr, pivotPos);
quickSort(arr + pivotPos + 1, size - pivotPos - 1);
@@ -51,7 +50,7 @@ void quickSort(T* arr, unsigned size)
int main()
{
std::vector<int> numbers;
- unsigned size = rand() % 10000;
+ size_t size = rand() % 10000;
numbers.resize(size);
for (size_t i = 0; i < size; i++)