Ir para conteúdo

POWERED BY:

Arquivado

Este tópico foi arquivado e está fechado para novas respostas.

Cartilho

Implementação do Radix sort

Recommended Posts

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

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

  • Conteúdo Similar

    • Por josenilson
      Olá pessoal !
       
      Estou tentando rodar um projeto de um jogo na minha maquina porem o mesmo pede para adicionar o log4cxx 0.10.0, realizei pesquisas na internet a respeito mas até agora nada, Encontre para baixar nesse site https://logging.apache.org/log4cxx/1.0.0/download.html porem não sei se devo instalar ele no windows porque ao exportar ele no projeto as depêndencias que precisam dele ficam informando o erro log4cxx.logger.h no such file or directory. a linguagem que estou usando e C++
       
       
    • Por biza
      Ola
      Estou  a construir um datalogger em código C.Desta forma necessito passar os dados entre ficheiros. O meu problema está na inclusão de algumas variáveis no topo de um arquivo .txt onde os dados são salvos. Variáveis como tempo de data e hora, id do dispositivo e muito mais... Para isso preciso de ajuda, gostaria que os dados estivessem disponíveis para todos os arquivos, até aí é fácil, basta incluir a variável como extern, no arquivos *.h e incluí-lo em todos os outros que você deseja que a variável esteja disponível. mas como posso fazer para ter acesso a ele dentro do array que preciso?
      Exemplo: main.c
      #include "main.h" char dateTimeFormat[24]; void main(void){ dateTimeFormat = "22-02-22 13:23:04"; } main.h
      extern char dateTimeFormat[24];  
      teste.c
       
      #include "main.h" extern char dateTimeFormat[24]; /*Header .txt file initialization*/ volatile char headerFile[] ="\n\n" "# HEALT MONITORING SYSTEM \r\n" "# DEVELOPED: BIZA \r\n" "# VERSION: B \r\n" "# DATATIMECAPTURE:"+dateTimeFormat+ "\r\n" "# SAMPLINGFREQUENCY: 500 \r\n" "# SAMPLECHANNELS: 1 2 3 4 5 6 7 8 \r\n" "# SAMPLINGRESULUTION: 24 \r\n" "# IDDEVICE: HEALTHY \r\n" "# ENDOFHEADER  
      Como posso incluir a variável "dateTimeFormat" dentro do headerFile como descrevi acima?
       
    • Por oromotoceu
      #include <stdio.h>
      #include <stdlib.h>
      #define MAXTAM 1000
      int Frente, Tras, Lista[MAXTAM];
      void Lista_Construtor(){
      Frente=0;
      Tras=-1;
      }
      int Lista_Vazia(){
      if(Tras==-1)
      return 1;
      else
      return 0;
      }
      int Lista_Cheia(){
      if(Tras==MAXTAM-1)
      return 1;
      else
      return 0;
      }
      int Lista_Tamanho(){
      return Tras+1;
      }
      int Lista_Inserir_Inicio(int Valor){
      if(Lista_Cheia()){
      return 0;
      }else{
      /*se quero inserir na posição 0,
      vou deslocar todos os elementos para frente*/
      for(int i=Tras+1;i>Frente;i--){
      Lista=Lista[i-1];
      }
      Lista[Frente]=Valor;
      Tras++;
      return 1;
        }
      }
      int Lista_Inserir_Fim(int Valor){
      if(Lista_Cheia()){
      return 0;
      }else{
      Tras++;
      Lista[Tras]=Valor;
      return 1;
        }
      }
      int Lista_Inserir(int Valor, int Posicao){
      if(Lista_Cheia()){
      return 0;
      }else{
      /* Para verificar se a posição
      está no meio da lista */
      if(Posicao>Frente && Posicao<Tras){
      for(int i=Tras+1;i>Posicao;i--){
      Lista=Lista[i-1];
      }
      Lista[Posicao]=Valor;
      Tras++;
      return 1;
      }else{ 
      return 0;
         }
        }
      }
      int Lista_Remover_Inicio(int *Valor){
      if(Lista_Vazia()){
      return 0;
      }else{
      *Valor =Lista[Frente];
      for(int i=Frente;i<Tras;i++){
      Lista=Lista[i+1];
         }
      Tras--;
        }
      }
      int Lista_Remover_Fim(int *Valor){
      if(Lista_Vazia()){
      return 0;
      }else{
      *Valor=Lista[Tras];
      Tras--;
      return 1;
        }
      }
      int Lista_Remover(int *Valor, int Posicao){
      if(Lista_Vazia()){
      return 0;
      }else{
      if(Posicao>Frente && Posicao<Tras){
      *Valor=Lista[Posicao];
      for(int i=Posicao;i<Tras;i++){
      Lista=Lista[i+1];
      }
      Tras--;
      return 1;
         }
        }
      }
      int Lista_Get_toda(int *Valor){
      if(Lista_Vazia()){
      return 0;
      }else{
      *Valor=Lista[Frente];
      return 1;
        }
      }
      int Lista_Get_inicio(int *Valor){
      if(Lista_Vazia()){
      return 0;
      }else{
      *Valor=Lista[Frente];
      return 1;
        }
      }
      int Lista_Get_Fim(int *Valor){
      if(Lista_Vazia()){
      return 0;
      }else{
      *Valor=Lista[Tras];
      return 1;
        }
      }
      int Lista_Busca_Valor(int Valor, int *Posicao){
      int i;
      if(Lista_Vazia()){
      return 0;
      }else{
      for(i=Frente;i<Tras;i++){
      if(Lista==Valor){
      break;
        }
      }
      if(i==Tras){
      return 0;
      }else{
      *Posicao=i; 
      return 1;
         }
        }
      }
      int Lista_Busca_Posicao(int *Valor, int Posicao){
      if(Lista_Vazia()){
      return 0;
      }else{
      if(Posicao>Frente && Posicao<Tras){
      *Valor=Lista[Posicao];
      return 1;
      }else{
      return 0;
         }
        }
      }
      int main(){
      int i,Valor,op=0,pos;
      Lista_Construtor();
      while(op!=12){
      printf("*** Menu de opções ***\n");
      printf("1-Inserir início\n");
      printf("2-Inserir fim\n");
      printf("3-Inserir meio\n");
      printf("4-Excluir início\n");
      printf("5-Excluir fim\n");
      printf("6-Excluir meio\n");
      printf("7-Mostrar toda lista\n");
      printf("8-Mostrar primeiro item da lista\n");
      printf("9-Mostrar último item da lista\n");
      printf("10-Mostrar a posição de um item da lista\n");
      printf("11-Mostrar o valor de uma posição\n");
      printf("12-Sair\n");
      printf("Escolha uma opção: ");
      scanf("%d", &op);
      switch(op){
          case 1:
              printf("Digite o valor a ser inserido: ");
              scanf("%d", &Valor);
              Lista_Inserir_Inicio(Valor);
              break;
          case 2:
              printf("Digite o valor a ser inserido: ");
              scanf("%d", &Valor);
              Lista_Inserir_fim(Valor);
              break;
            case 3:
              printf("Digite o valor a ser inserido: ");
              scanf("%d", &Valor);
              printf("Digite a posição que deseja inserir: ");
              scanf("%d", &pos);
              Lista_ Inserir_meio(int Valor, pos); 
              break;
            case 4:
              printf("Digite a remoção do início: ");
              scanf("%d", &*Valor);
              Lista_ Excluir_inicio(*Valor); 
              break;
              case 5:
              printf("Digite a remoção do fim: ");
              scanf("%d", &*Valor);
              Lista_ Excluir_fim(*Valor); 
              break;
              case 6:
              printf("Digite a remoção do meio: ");
              scanf("%d", &Valor);
              printf("Digite a posição que deseja remover: ");
              scanf("%d", &*Posicao);
              Lista_ Excluir_meio(intValor, * pos); 
              break;
               case 7:
              printf("Digite ao a mostrar toda lista: ");
              scanf("%d", &Valor);
              Lista_ mostrar_toda_lista(Valor);
              break;
             case 8:
              printf("Digite ao a mostrar primeiro item da lista: ");
              scanf("%d", &*Valor);
              Lista_ mostrar_primeiro_item_da_lista(*Valor);
              break;
             case 9:
              printf("Digite ao a mostrar último item da lista: ");
              scanf("%d", &*Valor);
              Lista_ mostrar_ultimo_item_da_lista(*Valor);
              break;
              case 10:
              printf("Digite ao a mostrar a posição de um item da lista: ");
              scanf("%d", &Valor);
              printf("Digite a posição que deseja mostrar na lista: ");
              scanf("%d", &* pos);
              Lista_ mostrar_posicao_de_um_item_da_lista(intValor, *pos);
              break;
              case 11:
              printf("Digite ao a mostrar o valor de uma posição: ");
              scanf("%d", &*Valor
              printf("Digite a posição que deseja mostrar no valor: ");
              scanf("%d", &pos);
              Lista_ mostrar_posicao_de_um_valor_da_lista(int*Valor, pos);
              break;
              case 12:
              default:
              printf("Valor Invalido!\n");
              system("PAUSE");
               }
         }
       return 0;
      }
    • Por oromotoceu
      bom dia pode me ajudar nessa questão por favor
      O programa deverá trabalhar dados de um veículo, onde será armazenado, Nome do proprietário, placa do carro, modelo do carro e preço do carro.
      O programa deve ter as seguintes opções:
      Inserir dados (todos os dados sugeridos no enunciado acima).
      Excluir um Carro específico com a busca pela placa.
      Editar dados de um Carro com a busca pela placa.
      Consultar carro por Placa.
      Exibir todos os dados cadastrados.
      Finalizar programa.
      A opção exibir todos os dados, apresenta tudo que já foi cadastrado e está na memória.
       
    • Por TK_T
      olá sou iniciante consegui fazer um o código de um exercício só que quando eu peço o valor 12ab ele lê como numérica alguém pode me ajudar? 
      Exercício: Leia uma string e diga se a mesma é numérica (na base decimal) ou não.
      Ex.: "123" -> numérica
      "abc" -> não numérica
      "12ab" -> não numérica
      "12.34" -> numérica 
      #include <stdio.h> int main() { char Numero; printf("Digite Algo: "); scanf("%c", &Numero); if(Numero == '1' || Numero == '2' || Numero == '3' || Numero == '4' || Numero == '5' || Numero == '6' || Numero == '7' || Numero == '8' || Numero== '9' || Numero == '0') printf("\tNumérica...\n"); else printf("\tNão Numérica\n"); return 0; }  
×

Informação importante

Ao usar o fórum, você concorda com nossos Termos e condições.