Code works sometimes yes and sometimes no

Question

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 above code for the Randomized-Select book algorithm Cormen algorithms and sometimes it runs sometimes does not run and gives segmentation failure.

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

Someone would have a suggestion on how to solve?

Answer 1

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

In his randomized_partition, what happens if r and p are the same? The interval will be zero and will give division by zero. That’s your mistake.

I think that what is below fixes the algorithm. I’m not sure, because I have no way to test it 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 have suspicions that your function Partition may be wrong, after all in the for (int j = p; j < r-1; j++), that means that j will of p until r - 2. I think it should be j < r or j <= r.