3

Esse é o meu código:

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

Fiz o código acima para o algoritmo Randomized-Select do livro algoritmos do Cormen e às vezes ele roda às vezes não roda e dá falha de segmentação.

Passei ele pelo GDB para isolar o problema e descobri que ele ocorre geralmente quando o intervalo fica muito pequeno, com 3 ou menos elementos e randomized_partition retorna um valor igual ao p ou r.

Alguém teria uma sugestão de como resolver?

1 Resposta 1

5

O srand(time(NULL)) só deveria ser chamado uma única vez, no main.

No seu randomized_partition, o que ocorre se r e p forem iguais? O interval será zero e vai dar divisão por zero. Esse é o seu erro.

Acho que isso que está abaixo conserta o algoritmo. Não tenho certeza, pois não tenho como testar agora, apenas acho.

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

Além disso, tenho suspeitas que a sua função Partition possa estar errada, afinal no for (int j = p; j < r-1; j++), isso significa que j irá de p até r - 2. Acho que deveria ser j < r ou j <= r.

2
  • Obrigado, aparentemente era isso mesmo que estava estava acontecendo, o intervalo estava igual a zero, quanto ao Partition esta assim por que se não ele troca o pivô com ele mesmo, na função randomized_partition o pivô e gerado aleatoriamente e posto na última posição, caso eu não fizesse ou j < r - 1 ele tentaria se trocar com ele mesmo e a variável i seria incrementada. Commented 24/12/2016 às 23:30
  • @PedroAbreuMaia Se a minha resposta te ajudou e você não tiver mais nada a questionar, poderia marcá-la como correta/aceita ao clicar no ✅ verde aqui ao lado? Commented 25/12/2016 às 1:36

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .