Ao executar o meu .cpp ele tem feito tudo corretamente com todos os metodos, menos o radix, ele tem q calcular os tempos e fazer a media depois, ele não tem feito isso com o radix e não sei oq fazer, preciso muito de ajuda e uma solução, ja tentei de tudo, mas não sou bom em C++.
link para ver funcionando: https://www.onlinegdb.com/fork/rkRmSLk24
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <chrono>
#include <unistd.h>
#include <iostream>
using namespace std;
int *v, *v1, *v2, *v3, *v4, *v5, *v6, *v7;
//-------------------------------------------------------------------------------------
void bubbleSort(int v[], int n)
{
bool trocou;
int k = n;
do {
trocou = false;
k--;
for (int i = 0; i < k; i++)
if (v[i+1] < v[i]) {
int aux = v[i+1];
v[i+1] = v[i];
v[i] = aux;
trocou = true;
}
} while (trocou);
}
//-------------------------------------------------------------------------------------
void insertionSort(int v[], int n)
{
int i, j, chave;
for (j = 1; j < n; j++) {
chave = v[j];
i = j - 1;
while (i >= 0 && v[i] > chave) {
v[i+1] = v[i];
i--;
}
v[i+1] = chave;
}
}
//-------------------------------------------------------------------------------------
void selectionSort(int v[], int n)
{
int i, j, min;
for(i = 0; i < n-1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (v[j] < v[min])
min = j;
if (min != i) {
int temp = v[min];
v[min] = v[i];
v[i] = temp;
}
}
}
//-------------------------------------------------------------------------------------
void shellSort(int v[], int n)
{
int i , j , valor;
int h = 1;
while(h < n) {
h = 3*h+1;
}
while (h > 1) {
h /= 3;
for(i = h; i < n; i++) {
valor = v[i];
j = i - h;
while (j >= 0 && valor < v[j]) {
v [j + h] = v[j];
j -= h;
}
v [j + h] = valor;
}
}
}
//-------------------------------------------------------------------------------------
void quickSort1(int v[], int ini, int fim)
{
int i = ini;
int j = fim;
int pivo = v[(ini+ fim)/2]; // Pivo e o elemento central
do
{
while (v[i] < pivo && i < fim)
i++;
while (pivo < v[j] && j > ini)
j--;
if (i <= j)
{
int aux = v[i];
v[i] = v[j];
v[j] = aux;
i++;
j--;
}
} while (i <= j);
if (ini < j)
quickSort1(v,ini,j);
if (i < fim)
quickSort1(v,i,fim);
}
void quickSort(int v[], int tam)
{
quickSort1(v, 0, tam-1);
}
//-------------------------------------------------------------------------------------
void intercala(int v[], int aux[], int ini, int meio, int fim)
{
int i = ini, j = fim, k;
for (k = ini; k <= meio; k++)
aux[k] = v[k];
for (k = meio+1; k <= fim; k++)
aux[fim + meio + 1 - k] = v[k];
for (k = ini; k <= fim; k++)
if (aux[i] <= aux[j])
v[k] = aux[i++];
else
v[k] = aux[j--];
}
void mergeSort1(int v[], int aux[], int ini, int fim)
{
if (ini < fim) {
int meio = (ini + fim) / 2;
mergeSort1(v, aux, ini, meio);
mergeSort1(v, aux, meio+1, fim);
intercala(v, aux, ini, meio, fim);
}
}
void mergeSort(int v[], int n)
{
int *aux = (int *) malloc(n * sizeof(int));
mergeSort1(v, aux, 0, n-1);
free(aux);
}
//-------------------------------------------------------------------------------------
int getMax(int v[], int tam)
{
int max = v[0];
for (int i = 1; i < tam; i++)
if (v[i] > max)
max = v[i];
return max;
}
void countSort(int v[], int tam, int exp)
{
int output[tam], i, count[10] = {0};
for (i = 0; i < tam; i++)
count[(v[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
count[i] += count[i-1];
for (i = tam - 1; i >= 0; i--)
{
output[count[(v[i] / exp) % 10] - 1] = v[i];
count[(v[i] / exp) % 10]--;
}
for (i = 0; i < tam; i++)
v[i] = output[i];
}
void radixsort(int v[], int tam)
{
int exp, m;
m = getMax(v, tam);
for (exp = 1; m/exp > 0; exp *= 10)
countSort(v, tam, exp);
}
//-------------------------------------------------------------------------------------
void gerar(int v[], int tam)
{
srand((unsigned int)time(NULL));
for (int i = 0; i < tam; i++)
v[i] = rand() % 100000001;
}
//-------------------------------------------------------------------------------------
void copiar(int origem[], int destino[], int n)
{
for (int i = 0; i < n; i++)
destino[i] = origem[i];
}
//-------------------------------------------------------------------------------------
bool verifica(int v[], int n)
{
for (int i = 0; i < n-1; i++)
if (v[i] > v[i+1])
return false;
return true;
}
//-------------------------------------------------------------------------------------
void inverte(int v[], int n)
{
for (int i = 0, j = n-1; i < n/2; i++,j--)
v[i] = v[j];
}
//-------------------------------------------------------------------------------------
int main(void)
{
chrono::steady_clock::time_point start, end;
long double cpu_time;
int tam, iter;
char metodos[100];
long double tempo[] = { 0, 0, 0, 0, 0, 0 };
tam = 0;
printf("Quantos numeros? ");
scanf("%d", &tam);
getchar();
if (tam <= 0)
return 0;
printf("Selecione os metodos:\n 1-Bubble sort\n 2-Selection sort\n 3-Insertion sort\n 4-Shell sort\n 5-Quicksort\n 6-Mergesort\n 7-Radix sort\nMetodos: ");
gets(metodos);
printf("Quantas execucoes (1, 2, 3, ...)? ");
scanf("%d", &iter);
getchar();
if (iter <= 0)
return 0;
v = (int *) malloc(tam * sizeof(int));
v1 = (int *) malloc(tam * sizeof(int));
v2 = (int *) malloc(tam * sizeof(int));
v3 = (int *) malloc(tam * sizeof(int));
v4 = (int *) malloc(tam * sizeof(int));
v5 = (int *) malloc(tam * sizeof(int));
v6 = (int *) malloc(tam * sizeof(int));
v7 = (int *) malloc(tam * sizeof(int));
for (int i = 1; i <= iter; i++) {
printf("------------------------------------------------\nExecucao %d:\n------------------------------------------------\n", i);
printf("Gerando %d elementos...\n", tam);
gerar(v, tam);
copiar(v, v1, tam);
copiar(v, v2, tam);
copiar(v, v3, tam);
copiar(v, v4, tam);
copiar(v, v5, tam);
copiar(v, v6, tam);
copiar(v, v7, tam);
// bubble
if (strchr(metodos, '1') != NULL) {
printf("Bubble sort...\n");
start = chrono::steady_clock::now();
bubbleSort(v1, tam);
end = chrono::steady_clock::now();
cpu_time = chrono::duration_cast<chrono::nanoseconds>(end - start).count() / (long double) 1000000.0;
printf("%s. Tempo: %lf ms (%lf s)\n", verifica(v1, tam) ? "OK":"ERRO", cpu_time, cpu_time/1000);
tempo[0] += cpu_time;
}
// selection
if (strchr(metodos, '2') != NULL) {
printf("Selection sort...\n");
start = chrono::steady_clock::now();
selectionSort(v3, tam);
end = chrono::steady_clock::now();
cpu_time = chrono::duration_cast<chrono::nanoseconds>(end - start).count() / (long double) 1000000.0;
printf("%s. Tempo: %lf ms (%lf s)\n", verifica(v3, tam) ? "OK":"ERRO", cpu_time, cpu_time/1000);
tempo[1] += cpu_time;
}
// insertion
if (strchr(metodos, '3') != NULL) {
printf("Insertion sort...\n");
start = chrono::steady_clock::now();
insertionSort(v2, tam);
end = chrono::steady_clock::now();
cpu_time = chrono::duration_cast<chrono::nanoseconds>(end - start).count() / (long double) 1000000.0;
printf("%s. Tempo: %lf ms (%lf s)\n", verifica(v2, tam) ? "OK":"ERRO", cpu_time, cpu_time/1000);
tempo[2] += cpu_time;
}
// shell
if (strchr(metodos, '4') != NULL) {
printf("Shell sort...\n");
start = chrono::steady_clock::now();
shellSort(v4, tam);
end = chrono::steady_clock::now();
cpu_time = chrono::duration_cast<chrono::nanoseconds>(end - start).count() / (long double) 1000000.0;
printf("%s. Tempo: %lf ms (%lf s)\n", verifica(v4, tam) ? "OK":"ERRO", cpu_time, cpu_time/1000);
tempo[3] += cpu_time;
}
// quick
if (strchr(metodos, '5') != NULL) {
printf("Quick sort...\n");
start = chrono::steady_clock::now();
quickSort(v5, tam);
end = chrono::steady_clock::now();
cpu_time = chrono::duration_cast<chrono::nanoseconds>(end - start).count() / (long double) 1000000.0;
printf("%s. Tempo: %lf ms (%lf s)\n", verifica(v5, tam) ? "OK":"ERRO", cpu_time, cpu_time/1000);
tempo[4] += cpu_time;
}
// merge
if (strchr(metodos, '6') != NULL) {
printf("Merge sort...\n");
start = chrono::steady_clock::now();
mergeSort(v6, tam);
end = chrono::steady_clock::now();
cpu_time = chrono::duration_cast<chrono::nanoseconds>(end - start).count() / (long double) 1000000.0;
printf("%s. Tempo: %lf ms (%lf s)\n", verifica(v6, tam) ? "OK":"ERRO", cpu_time, cpu_time/1000);
tempo[5] += cpu_time;
}
//radixsort
if (strchr(metodos, '7') != NULL) {
printf("Radix sort...\n");
start = chrono::steady_clock::now();
radixsort(v7, tam);
end = chrono::steady_clock::now();
cpu_time = chrono::duration_cast<chrono::nanoseconds>(end - start).count() / (long double) 1000000.0;
printf("%s. Tempo: %lf ms (%lf s)\n", verifica(v7, tam) ? "OK":"ERRO", cpu_time, cpu_time/1000);
tempo[6] += cpu_time;
}
}
if (iter > 1) {
printf("-------------------------------------------\nTempos medios:\n");
if (strchr(metodos, '1') != NULL)
printf("Bubble sort: %lf ms (%lf s)\n", tempo[0]/iter, tempo[0]/(iter*1000));
if (strchr(metodos, '2') != NULL)
printf("selection sort: %lf ms (%lf s)\n", tempo[1]/iter, tempo[1]/(iter*1000));
if (strchr(metodos, '3') != NULL)
printf("Insertion sort: %lf ms (%lf s)\n", tempo[2]/iter, tempo[2]/(iter*1000));
if (strchr(metodos, '4') != NULL)
printf("Shell sort: %lf ms (%lf s)\n", tempo[3]/iter, tempo[3]/(iter*1000));
if (strchr(metodos, '5') != NULL)
printf("Quick sort: %lf ms (%lf s)\n", tempo[4]/iter, tempo[4]/(iter*1000));
if (strchr(metodos, '6') != NULL)
printf("Merge sort: %lf ms (%lf s)\n", tempo[5]/iter, tempo[5]/(iter*1000));
if (strchr(metodos, '7') != NULL)
printf("Radix sort: %lf ms (%lf s)\n", tempo[6]/iter, tempo[6]/(iter*1000));
}
free(v);
free(v1);
free(v2);
free(v3);
free(v4);
free(v5);
free(v6);
free(v7);
}
