0

Optimization

I got a homework assignment, I need to fill an array with no repeated random integers between 0 and the max-size of the array (e.g. [3, 1, 2, 0] (size 4), [1, 3, 2] (size 3)) I've done this before, but now I got to do it without the [i] index for the array, I need to do it with pointers and I did it, but I wonder if there is a better way to do it, more optimized or something like that, my code is:

void fillingArray (int *arr) {
    int *firstElementOfArray = arr;
    int *lastIndexedElement = arr;
    int randomNumber;
    bool repeated;
    for (int i = 0; i < MAX_SIZE; ++i) {
        do {
            randomNumber = randNumber(MAX_SIZE);
            repeated = false;
            for (int *j = firstElementOfArray; j < lastIndexedElement; ++j) {
                if (*j == randomNumber) {
                    repeated = true;
                    break;
                }
            }
        } while (repeated);
        *arr = randomNumber;
        arr++;
        lastIndexedElement++;
    }
}
Ricardo Roel
  • 1
  • 3
  • 3
    One way to do it is to fill the array with the numbers you want in sequence and then shuffle the array. [Unique (non-repeating) random numbers in O(1)?](https://stackoverflow.com/questions/196017/unique-non-repeating-random-numbers-in-o1) – Retired Ninja Jun 09 '23 at 01:36
  • Any reasonable implementation of this should run in linear time, i.e. O(n). The posted code runs in quadratic time, i.e. O(n^2), at best. In fact, it's worse than that since you will get more and more collisions causing it to have to retry. That means you're using a bad algorithm. In particular, there is no need for nested loops. Try to do it with no nested loops. Hint: You can do it in two passes. The first just fills in the values in sequence from 0 through n-1. The second shuffles them in-place. Each pass can be done with a single, non-nested loop. – Tom Karzes Jun 09 '23 at 02:05

0 Answers0