path: root / Year 2 / Design and analysis of algorithms / Practicum / Action-128.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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);
}