diff options
1 files changed, 38 insertions, 0 deletions
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Practicum/Action-128.cpp | 38 |
diff --git a/Year 2/Design and analysis of algorithms/Practicum/Action-128.cpp b/Year 2/Design and analysis of algorithms/Practicum/Action-128.cpp new file mode 100644 index 0000000..414b43a --- /dev/null +++ b/Year 2/Design and analysis of algorithms/Practicum/Action-128.cpp @@ -0,0 +1,38 @@ +#include <stdio.h> +#include <algorithm> +using namespace std; + +int people[100010] = { 0 }; +int counter = 0; + +void quickSort(int start, int end) { + if (start >= end) return; + int pivot = people[(end - start) / 2]; + for (int l = start, r = end; l < r; ) { + if (people[l] < people[pivot]) { + l++; + continue; + } + if (people[r] > people[pivot]) { + r--; + continue; + } + counter++; + swap(people[l], people[r]); + } + + quickSort(start, pivot - 1); + quickSort(pivot + 1, end); +} + +int main() { + int n; + scanf("%d", &n); + for (int i = 0; i < n; i++) { + scanf("%d", &people[i]); + } + + quickSort(0, n-1); + + printf("%d\n", counter); +} |
