rendered paste body#include <stdio.h>#include <stdlib.h>#include <time.h>#include <sys/time.h>int *a, *b, *aux;int argMin(int p, int r) { int min, i; min = p; for (i = p + 1; i <= r; i++) if (b[i] < b[min]) min = i; return min;}void swap(int i, int j) { int aux; aux = b[i]; b[i] = b[j]; b[j] = aux;}int partition(int p, int r) { int x, i, j; x = b[r]; i = p - 1; for (j = p; j < r; j++) if (b[j] <= x) swap(++i, j); swap(i+1, r); return i+1;}void printArray(int n) { int i; for (i = 0; i < n; i++) printf("%d ", b[i]); printf("\n");}void intercala(int p, int q, int r) { int i, j, k; for (i = p; i <= q; i++) aux[i] = b[i]; for (j = q + 1; j <= r; j++) aux[r + q + 1 - j] = b[j]; i = p; j = r; for (k = p; k <= r; k++) { if (aux[i] <= aux[j]) b[k] = aux[i++]; else b[k] = aux[j--]; }}void mergeSort(int p, int r) { int q; if (p < r) { q = (p + r)/2; mergeSort(p, q); mergeSort(q+1, r); intercala(p, q, r); }}void veryQuickSort(int p, int r) { int m, k, q; if (p < r) { k = (p + 2 * r)/3; m = argMin(k, r); swap(m, k); q = partition(p, k); veryQuickSort(p, q-1); veryQuickSort(q+1, k); veryQuickSort(k+1, r); intercala(q, k, r); }}void quickSort(int p, int r) { int q; if (p < r) { q = partition(p, r); quickSort(p, q-1); quickSort(q+1, r); }}struct timeval start;void stopw_start() { gettimeofday(&start, NULL);}void stopw_stop() { struct timeval end; gettimeofday(&end, NULL); printf("%ld microseconds\n", 1000000 * (end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec));}void copy(int *src, int *dest, int n) { int i; for (i = 0; i < n; i++) dest[i] = src[i];}int main(int argc, char **argv) { int i, mod, max; if (argc < 2 || (max = atoi(argv[1])) == -1) { printf("Forneça o tamanho do vetor.\n"); exit(1); } /* Vetor aleatório */ a = malloc(max * sizeof(*a)); /* Cópia do vetor acima */ b = malloc(max * sizeof(*b)); /* Vetor auxiliar */ aux = malloc(max * sizeof(*aux)); srand(time(NULL)); mod = max * max * max; for (i = 0; i < max; i++) { a[i] = rand() % mod; b[i] = a[i]; } /*printf("Vetor aleatório: "); printArray(max);*/ printf("VeryQuickSort: "); stopw_start(); veryQuickSort(0, max - 1); stopw_stop(); copy(a, b, max); printf("MergeSort: "); stopw_start(); mergeSort(0, max - 1); stopw_stop(); copy(a, b, max); printf("QuickSort: "); stopw_start(); quickSort(0, max - 1); stopw_stop(); free(a); free(aux); free(b); return 0;}