jeudi 1 avril 2021

Randomized algo (randomized pivot selection) gives different output everytime i run the program

I am dealing with a large data set, so i decided to implement the linear selection algorithm which is derived from the quick sort algorithm, as it gives the nth smallest element from an array in almost linear time. Here is my implementation:

long Random(long lower, long upper)
{
    long num = (rand() % (upper - lower + 1)) + lower;
    return num;
}
long partition(long arr[], long l, long r, long pivot)
{
    long j = l;
    long pi = arr[pivot];
    swap(&arr[pivot], &arr[r]);
    for (int i = l; i < r; i++)
    {
        if ((arr[i] < pi) && (j != i))
        {
            swap(&arr[j], &arr[i]);
            j++;
        }
    }
    swap(&arr[r], &arr[j]);
    return j;
}

long select(long arr[], long l, long r, long n, int i)
{
    if (n == 1)
    {
        return arr[0];
    }
    long pivot = Random(l, r);
    long x = partition(arr, l, r, pivot);
    if (x == i)
    {
        return arr[x];
    }
    else if (x > i)
    {
        return select(arr, l, x, (x - 1), i);
    }
    else
    {
        return select(arr, x, r, (n - x), (i - x));
    }
}

int main(void)
{
    srand(time(0));
    FILE *f;
    f = fopen("integers.txt", "r");
    long arr[SIZE];

    for (int i = 0; i < SIZE; i++)
    {
        fscanf(f, "%ld", &arr[i]);
    }
    fclose(f);

    long in;
    cout << "Enter the index you want to find - ";
    cin >> in;
    cout << select(arr, 0, (SIZE - 1), SIZE, (in - 1)) << endl;
}

Not only it gives the incorrect answer, it gives a different answer every time. I have no clue why, is there something wrong in the way i have used srand and rand functions, or is their something else wrong with my algorithm?

Thank You in advance




Aucun commentaire:

Enregistrer un commentaire