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?