From df74c873bc11ad90fb26e582c7be0ed092228661 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Fri, 25 Oct 2024 18:04:36 -0400 Subject: Add sem03 --- Seminar02/README.md | 17 ++++++++++++++++- Seminar02/src/sorting-algorithms/quick-sort.cpp | 7 +++---- 2 files changed, 19 insertions(+), 5 deletions(-) (limited to 'Seminar02') 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 size_t partition(T* pArr, size_t len) { @@ -37,12 +36,12 @@ size_t partition(T* pArr, size_t len) } template -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 numbers; - unsigned size = rand() % 10000; + size_t size = rand() % 10000; numbers.resize(size); for (size_t i = 0; i < size; i++) -- cgit v1.3.1-26-gb76a