Implementação do Radix sort

[Implementação do Radix sort]

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);
}