Jump to content

Cartilho

Members
  • Content count

    1
  • Joined

  • Last visited

Community Reputation

0 Comum

About Cartilho

  1. Cartilho

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

Important Information

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