# Cod sursa(job #1813849)

Utilizator Data 23 noiembrie 2016 13:56:22 Sortare prin comparare 100 cpp done Arhiva educationala 1.51 kb
``````#include <cstdio>
#include <ctime>
#include <cstdlib>
#define NMAX 500010
using namespace std;

int A[NMAX], B[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 merge(int A[], int left, int mid, int right) {
int i, j, k, aux;

for (i = k = left, j = mid + 1; i <= mid || j <= right;) {
if (j > right || (i <= mid && A[i] <= A[j])) {
B[k++] = A[i++];
} else {
B[k++] = A[j++];
}
}

for (k = left; k <= right; k++) {
A[k] = B[k];
}
}

void merge_sort(int A[], int left, int right) {
if (left < right) {
int mid = (left + right) >> 1;
merge_sort(A, left, mid);
merge_sort(A, mid + 1, right);
merge(A, left, mid, right);
}
}

void sort_array(int A[], int N) {
//quick_sort(A, 1, N);
merge_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;
}``````