Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
1 files changed, 38 insertions, 0 deletions
-rw-r--r--Year 2/Design and analysis of algorithms/Practicum/Action-128.cpp38
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);
+}