# Cod sursa(job #1813832)

Utilizator Data 23 noiembrie 2016 13:38:36 Sortare prin comparare 80 cpp done Arhiva educationala 0.99 kb
``````#include <cstdio>
#include <ctime>
#include <cstdlib>
#define NMAX 500010
using namespace std;

int A[NMAX], i, N;

int partition(int A[], int left, int right) {
int p = left + rand() % (right - left + 1);
int i = left, j = right, aux = 0;

aux = A[left]; A[left] = A[p]; A[p] = aux;
while (i < j) {
while (A[i] <= A[left] && i < j) ++i;
while (A[j] > A[left]) --j;
if (i < j) {
aux = A[i]; A[i] = A[j]; A[j] = aux;
}
}

aux = A[left]; A[left] = A[j]; A[j] = aux;
return j;
}

void quick_sort(int A[], int left, int right) {
if (left < right) {
int p = partition(A, left, right);
quick_sort(A, left, p - 1);
quick_sort(A, p + 1, right);
}
}

void sort_array(int A[], int N) {
quick_sort(A, 1, N);
}

int main() {
srand(time(0));

freopen("algsort.in", "r", stdin);
freopen("algsort.out", "w", stdout);

scanf("%d", &N);
for (i = 1; i <= N; i++) {
scanf("%d", &A[i]);
}

sort_array(A, N);

for (i = 1; i <= N; i++) {
printf("%d ", A[i]);
}

printf("\n");
return 0;
}``````