0
I’m having trouble with this code... when I run it it’s returning me to negative run time. He was supposed to show me the execution time of each method. And not being able to change the function 'generate' (responsible for the generation of random values of the vectors), so that numbers are generated in the range from 0 to 100,000,000.
the problem may be in the Radix Sort method
The code is in the js tab, but is not executable, it is a . cpp
#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);
}
//-------------------------------------------------------------------------------------
void radixsort(int v[], int tam) {
int i;
int *b;
int maior = v[0];
int exp = 1;
b = (int *)calloc(tam, sizeof(int));
for (i = 0; i < tam; i++) {
if (v[i] > maior)
maior = v[i];
}
while (maior/exp > 0) {
int bucket[10] = { 0 };
for (i = 0; i < tam; i++)
bucket[(v[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = tam - 1; i >= 0; i--)
b[--bucket[(v[i] / exp) % 10]] = v[i];
for (i = 0; i < tam; i++)
v[i] = b[i];
exp *= 10;
}
free(b);
}
//-------------------------------------------------------------------------------------
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);
}
If you want to generate random numbers between 0 and 100,000,000 use: v[i] = Rand() % 100000001;
– anonimo
I changed, but still continues the problem of the team coming negative.. there is no way to be sure q worked...
– Pedro Castilho
I’m pretty sure the error this in the Radix Sort method... is that I know the least...
– Pedro Castilho