Cod sursa(job #2142126)

Utilizator Data 24 februarie 2018 19:16:23 Sortare prin comparare 100 cpp done Arhiva educationala 1.59 kb
``````#include<iostream>
#include<cstdlib>
#include<time.h>
#include<algorithm>
#include<vector>
using namespace std;

int partition(vector<int> &A, int start, int end) {
int p = start + rand() % (end - start + 1);
int aux = A[p]; A[p] = A[end]; A[end] = aux;
int i = start;

for (int j = start; j < end; j++) {
if (A[j] <= A[end]) {
aux = A[i]; A[i] = A[j]; A[j] = aux;
i++;
}
}

aux = A[i]; A[i] = A[end]; A[end] = aux;
return i;
}

void quick_sort(vector<int> &A, int start, int end) {
if (start < end) {
int p = partition(A, start, end);
quick_sort(A, start, p - 1);
quick_sort(A, p + 1, end);
}
}

void merge_arrays(vector<int> &A, int start, int mid, int end) {
vector<int> B(end - start + 1);
int i = start, j = mid + 1, k = 0;

while (i <= mid || j <= end) {
if (j > end || (i <= mid && A[i] <= A[j])) B[k++] = A[i++];
else B[k++] = A[j++];
}

for (i = start; i <= end; i++) {
A[i] = B[i - start];
}
}

void merge_sort(vector<int> &A, int start, int end) {
if (start < end) {
int m = start + (end - start) / 2;
merge_sort(A, start, m);
merge_sort(A, m + 1, end);
merge_arrays(A, start, m, end);
}
}

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

srand(time(0));

int N;
cin>>N;

vector<int> A(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
}

merge_sort(A, 0, N - 1);

for (int i = 0; i < N; i++) {
cout << A[i] << ' ';
}

return 0;
}
``````