Code works sometimes yes and sometimes not

Question

Code works sometimes yes and sometimes not

Navigation

#1 by (5 votes)

3

This is my code:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void exchange (int *arr, int i, int j)
{
    if (i == j)
        return;
    int aux = arr[j];
    arr[j] = arr[i];
    arr[i] = aux;
}

int Partition (int *arr, int p, int r)
{
    int i, x;
    x = arr[r-1];
    i = p - 1;
    for (int j = p; j < r-1; j++)
    {
        if (arr[j] <=  x)
            exchange (arr, ++i, j);
    }
    exchange (arr, ++i, r-1);
    return i;
}

int randomized_partition (int *arr, int p, int r)
{
    int i, interval;
    interval = (r - p);
    srand(time(NULL));
    i = (rand() % interval) + p;
    exchange (arr, i, r-1);
    return Partition(arr, p, r);
}

int randomized_select (int *arr, int p, int r, int i)
{
    if (p == r)
        return arr[p];
    int k, q;    
    q = randomized_partition (arr, p, r);    
    k = q - p;
    if (i == k)
        return arr[q];
    else if (i < k)
        return randomized_select (arr, p, q, i);
    else
        return randomized_select (arr, q, r, i - k);
}

void selectionsort(int *arr, int qtd)
{
    int i, j, smaller, smallerpos;
    for(i = 0; i < qtd; i++)
    {
        smaller = 1000, smallerpos = -1;
        for(j = i; j < qtd; j++)
        {
            if(arr[j] < smaller)
            {
                smaller = arr[j];
                smallerpos = j;
            }
        }
        exchange (arr, i, smallerpos);
    }
}

int main ()
{
    int tam, k, *entrada, *teste;
    cin >> tam;
    cin >> k;
    entrada = new int[tam];
    teste = new int[tam];

    for (int i = 0; i < tam; i++)
    {
        entrada[i] = rand()%100;
        teste[i] = entrada[i];
        if (i % 10 == 0)
            cout << endl;
        cout << entrada[i] << " ";
    }

    selectionsort (teste, tam);

    cout << endl;

    for (int i = 0; i < tam; i++)
    {
        if (i % 10 == 0)
            cout << endl;
        cout << teste[i] << " ";
    }

    cout << endl;

    cout << randomized_select (entrada, 0, tam, k) << endl;
    return 0;
}

I made the code above for the Randomized-Select algorithm of the Cormen algorithm book and sometimes it does not run and it does not spin and it fails to target.

I passed it through GDB to isolate the problem and found that it usually occurs when the interval gets too small with 3 or fewer elements and randomized_partition returns a value equal to p or r .

Would anyone have a suggestion of how to solve?

c++ algoritmo

asked by anonymous 24.12.2016 / 20:56

1 answer

How to know if at the beginning of a p have "x" character? Doubt angularjs with array

score 5 · Accepted Answer

The srand(time(NULL)) should only be called once, in main .

In its randomized_partition , what happens if r and p are the same? The interval will be zero and will divide by zero. This is your mistake.

I think this is what fixes the algorithm. I'm not sure, because I can not test now, I just think.

int randomized_partition (int *arr, int p, int r)
{
    int i, interval;
    interval = (r - p);
    if (interval == 0) return p;
    i = (rand() % interval) + p;
    exchange (arr, i, r-1);
    return Partition(arr, p, r);
}

Also, I suspect that your Partition function might be wrong, after all in for (int j = p; j < r-1; j++) , it means that j will go from p to r - 2 . I think it should be j < r or j <= r .