include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
const int N = (int)1e6 + 10;
using namespace std;
int arr[N] = {0};
void quick_sort(int arr[], int left, int right);
int main() {
int n = 0;
scanf(“%d”, &n);
for (int i = 1; i <= n; i) scanf(“%d”, arr + i);
quick_sort(arr, 1, n);
for (int i = 1; i <= n; i) printf(“%d “, arr[i]);
return 0;
}
void quick_sort(int arr[], int left, int right) {
if (left >= right) return;
int idx = rand() % (right - left + 1) + left;
int x = arr[idx], i = left - 1, j = right + 1;
while (i < j) {
do j–; while (arr[j] > x);
do i++; while (arr[i] < x);
if (i < j) swap(arr[i], arr[j]);
}
quick_sort(arr, left, j), quick_sort(arr, j + 1, right);
}