Radix-Sort method does not work properly!

Asked

Viewed 68 times

-1

[.cpp has to measure and average the processing time of the implementation methods]

After implementing the Radix all stopped timing the time correctly.

The program asks how many numbers and how many runs, it only runs 1x in Radix.

Possible error location between lines 161-197 (location where Radix is located)

link to see how it works: https://www.onlinegdb.com/fork/rkRmSLk24

Part where the mistake is possible (lines 161-197)

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

complete code (all commented code and easy localization of the implementations):

#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);
}
c c++

  • Possible duplicate of Problem with implementation of Radix Sort

  • Please do not duplicate questions. If the previous question was not well received, you must edit it and fix problems (including several comments there explaining what/how to fix).

  • I tidied it up and left it in the form you asked for, so I created another

  • Even if you deleted the previous question, this one is practically identical, and therefore with the same problems already pointed out... If you’re going to post again, at least try to follow the guidelines that were given earlier (such as reducing the code to a [mcve])

  • Maybe the first time he arrives on Earth Goku will kill him with Piccolo’s help

1 answer

0

I didn’t find any error in your method radixsort() and how the duration interval is calculated separately for each of the functions invoked, I cannot imagine how the implementation of that particular method could impact the output of the program when other methods are invoked.

Anyway, I tested your program in Codeblocks (Windows 10 OS) and, interestingly, it worked by correctly informing the execution interval of each Sorting method. So I went to check what was wrong with the environment you left the link. I entered the following code in the area of main() reserved for the Buble Sort method: 

//verifica e imprime time_clock armazenado na variável start
auto st = start.time_since_epoch();
 int startInt = std::chrono::duration_cast<chrono::nanoseconds>(st).count();
 std::cout << "start == " << startInt << std::endl;

//verifica e imprime time_clock armazenado na variável end
 auto en = end.time_since_epoch();
 int endInt = std::chrono::duration_cast<chrono::nanoseconds>(en).count();
 std::cout << "end == " << endInt << std::endl;
//[...]
//imprime valor armazenado na varíavel cpu_time
std::cout << "cpu time == " << cpu_time << std::endl;

The output of the program, choosing the option 10,000 numbers with Buble Sort, was:

Gerando 10000 elementos...                                                                                            
Bubble sort...                                                                                                        
start == 21427696                                                                                                     
end == 644719493                                                                                                      
cpu time == 623.292                                                                                                   
OK. Tempo: 0.000000 ms (0.000000 s)

Based on this result, it seems clear to me that the program, in the implementation you have indicated, correctly calculates and stores the time interval. Therefore, I imagine that the error is occurring in the output of this value, ie in the function printf()

Luckily, when I was entering the debug code, I made a syntax error and the interpreter, in addition to indicating my syntax error, reported the following warning:

main.cpp:821:16: warning: format '%lf' expects argument of type 'double', but argument 4 has type 'long double' [-Wformat=]
main.cpp:864:16: warning: format '%lf' expects argument of type 'double', but argument 3 has type 'long double' [-Wformat=]
 cpu_time / 1000);

The warning repeats for the other times that the printf() is invoked.

Finally, perhaps, you are wondering: and how to fix this? in other words, what is the appropriate format for printf() print a long double? This issue is problematic because some implementations do not have support for long double, for more details take a look at this issue: printf and long double.

So the easiest way would be to simply replace the variable long double cpu_time for double cpu_time. I did it in the link you passed and your program worked as expected.

Browser other questions tagged c c++

You are not signed in. Login or sign up in order to post.