Jump to content
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);
}

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Similar Content

    • By andreluizsgf
      Boa noite, eu estou tentando implementar uma função que imprima uma árvore como ela deveria ser, com o pai acima e a direita do menor filho e acima e a esquerda do maior filho. 
      Já tenho duas funcões que me permitem imprimir por nível, porém estou tentando adaptá-las para a impressão correta. Exemplo:
      árvore: 5,4,3,2,1;
      Impressão:
                  5
          3             4
      1      2

      O código para o print é este:
       
      void ---ivel(node_t* raiz, int level) { if (raiz == NULL){ for(int i = 0 ; i < 3 ; i++){ printf("\t"); return;} } if (level == 1) { for (int i=0; i<altura(raiz); i++) printf("\t"); simpleprint(raiz); } else if (level > 1) { ---ivel(raiz->left, level-1); ---ivel(raiz->right, level-1); } }   void printarordem(node_t *raiz) { int h = altura(raiz); int i; for (i=1; i<=h; i++) { printf("\t"); ---ivel(raiz, i); printf("\n"); } }

      Se alguém souber como resolver este ou sugerir outra implementação, fico super agradecido! 
    • By vinicius.benedito98
      Faça um Programa em Linguagem C que receba o nome e a nota de 180 alunos de uma sala e armazene em vetor. Calcule e mostre: 
      - A média da sala; 
      - O nome do aluno com a maior nota; 
      - O nome do aluno com a menor nota; 
      - Os nomes dos alunos aprovados;

      O meu código é esse :

      #define N 180 
      int main() { 
      int i, ind_maior, ind_menor; 
      float nota[N], soma=0, media, min_aprov=7; 
      char nome[N][50]; 
      for (i=0; i printf("Informe o nome do %dº aluno: ", i+1); 
      gets(nome); 
      printf("Informe a nota do %dº aluno: ", i+1); 
      scanf(" %d ", &nota); 
      soma += nota; 

      media = soma / N; 
      printf("\nMédia da sal: %.2f\n", media); 
      ind_menor = ind_maior = 0; 
      for (i=1; i if (nota < nota[ind_menor]) 
      ind_menor = i; 
      if (nota > nota[ind_maior]) 
      ind_maior = i; 

      printf("Menor nota: %s com %.2f\n", nome[ind_menor], nota[ind_menor]); 
      printf("Maior nota: %s com %.2f\n", nome[ind_maior], nota[ind_maior]); 
      printf("Aprovados:"); 
      for (i=0; i if (nota >= min_aprov) 
      printf("\t%s com: %.2f\n", nome, nota); 

      return 0; 
      }


      Porém quando vou executa-lo, o programa pede para inserir o nome e nota do aluno apenas uma vez, e fica por isso, ele não exibe os resultados, alguém pode me ajudar ?
    • By WizardTech
      Eu estou criando uma aplicação cliente/servidor em C no ubuntu. O propósito é bem simples, saber se vale mais a pena alugar ou vender um imóvel, o usuário digita o valor do aluguel, os meses que irá alugar e o valor que irá vender e o servidor faz as contas e devolve o resultado. Tudo está dentro de um do while para ficar infinito, no final o usuário digita CONTINUAR para testar outros valores e SAIR para encerrar a conexão. Mas está com um problema que não consigo identificar. A primeira vez que comparamos valores, o servidor retorna o resultado correto(alugar ou vender), porém a partir da segunda vez ao digitar CONTINUAR, ele sempre retorna resultados errados. Eu suspeito que esteja armazenando dados na variáveis erradas a partir da segunda vez, coloquei uns prints no meio do código para mostrar os valores e tem divergência.E também tentei zerar as variáveis no começo e usar vários bzero e fflush, mas sem resultado. Mas não tenho certeza de nada. Podem me ajudar?
       
      CÓDIGO DO CLIENTE:
      #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <netdb.h> #include <stdio.h> #include <stdlib.h> #include <strings.h> #include <string.h>  int main () { struct sockaddr_in sock; int con, sockid,numbytes; char resposta[10]; char buf[100]; char aluguel[10]; char venda[10]; char meses[2]; sockid = socket(AF_INET, SOCK_STREAM, 0); bzero(&(sock),sizeof(sock)); sock.sin_family = AF_INET; sock.sin_port = htons(9012); inet_pton(AF_INET, "127.0.0.1",&sock.sin_addr); con=connect(sockid,(struct sockaddr*)&sock,sizeof(sock)); do{ if(con>=0) { printf("=====================================================\n"); printf("Descubra se vale a pena vender ou alugar seu imóvel\n"); printf("=====================================================\n"); printf("Digite por quanto voce quer alugar: \n"); scanf("%s", &aluguel); printf("=====================================================\n"); if(send(sockid,aluguel,strlen(aluguel),0)==-1) { printf("Erro ao enviar mensagem\n"); close(sockid); } printf("Digite por quantos meses ira alugar : \n"); scanf("%s", &meses); printf("=====================================================\n"); if(send(sockid,meses,strlen(meses),0)==-1) { printf("Erro ao enviar mensagem\n"); close(sockid); } printf("Digite por quanto quer vender: \n"); scanf("%s", &venda); printf("=====================================================\n"); if(send(sockid,venda,strlen(venda),0)==-1) { printf("Erro ao enviar mensagem \n"); close(sockid); } bzero(&buf,sizeof(buf)); if((numbytes=recv(sockid,buf,100,0)==-1)) { printf("Erro ao receber a mensagem\n"); } printf("Vale mais a pena: %s\n",buf); printf("Digite SAIR para sair ou CONTINUAR para continuar a comparar.\n"); scanf("%s",&resposta); fflush(stdin); if(send(sockid,resposta,strlen(resposta),0)==-1) { printf("Erro ao enviar mensagem\n"); close(sockid); } if(strcmp(resposta,"CONTINUAR")==0) { continue; } } }while(strcmp(resposta,"SAIR")!=0); close(sockid); }  
      CÓDIGO DO SERVIDOR:
      #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <netdb.h> #include <stdio.h> #include <stdlib.h> #include <strings.h> #include <string.h> int main () { int sockid; struct sockaddr_in servidor; int client,numbytes; float convertido; float convertido1; float convertido2; char passar[10]; char buf[100]; char buf1[100]; char buf2[100]; float resultado; char resposta[10];  sockid = socket(AF_INET, SOCK_STREAM,0); if(sockid==-1) { printf("Não foi possivel criar o socket"); exit(1); } servidor.sin_family= AF_INET; servidor.sin_addr.s_addr = htonl(INADDR_ANY); servidor.sin_port = htons(9012); if(bind(sockid,(struct sockaddr*)&servidor, sizeof(servidor))<0) { printf("Falhou ao associar a porta\n"); } listen(sockid, 3); int c, new_socket; while(1) { c = sizeof(struct sockaddr_in); new_socket = accept(sockid, (struct sockaddr *)&client,(socklen_t *)&c); if(new_socket <=0) { printf("Falhou ao aceitar o conector\n"); continue; } while(1){ printf("Conexão aceita\n"); fflush(stdin); resultado = 0; convertido = 0; convertido1 = 0; convertido2 = 0; bzero(&buf,sizeof(buf)); if((numbytes=recv(new_socket,buf,100,0)==-1)) { printf("Erro ao receber a mensagem\n"); } convertido = atof(buf); bzero(&buf1,sizeof(buf1)); if((numbytes=recv(new_socket,buf1,100,0)==-1)) { printf("Erro ao receber mensagem\n"); } convertido1 = atof(buf1); printf(buf1); bzero(&buf2,sizeof(buf2)); if((numbytes=recv(new_socket,buf2,100,0)==-1)) { printf("Erro ao receber mensagem\n"); } convertido2 = atof(buf2); printf(buf2);  resultado = convertido*convertido1; if(resultado>convertido2) { sprintf(passar, "Alugar"); } else { sprintf(passar,"Vender"); } if(send(new_socket,passar,strlen(passar),0)==-1) { printf("Erro ao enviar a mensagem\n"); close(new_socket); } bzero(&resposta,sizeof(resposta)); if((numbytes=recv(new_socket,resposta,strlen(resposta),0)==-1)) { printf("Erro ao receber a mensagem\n"); } fflush(stdin); if(strcmp(resposta,"SAIR")==0) {  close(new_socket); break; }  } }  }  
×

Important Information

Ao usar o fórum, você concorda com nossos Terms of Use.