Removing duplicate entries in an array (C++)

Question

I'm having an issue in which a function that in theory should remove all duplicate values from an array doesn't work. Here's how it works:

1. I have two arrays, and then I populate them with random numbers between 0 and 50 inclusive.
2. I sort the array values in order using a sort function
3. I then run my dedupe function
4. I sort the array values in order again
5. I then output the values in both arrays

The problem is, the loop in the dedupe function is ran 19 times regardless of how many duplicate entries it finds, which is extremely strange. Also, it still gives duplicates.

Any ideas? Thanks!

int* dedupe(int array[ARRAY_SIZE])      //remove duplicate array values and replace with new values.
{   bool dupe = false;
    while(dupe!=true)
    {   
        for(int j=0; j<ARRAY_SIZE; j++)
        {   if(array[j] == array[j+1])
            {   array[j] = rand(); 
                array[j] = array[j] % 51;
                dupe = false;
            }
            else { dupe = true; // the cout part is for debugging
                    cout << dupe << endl; }
        }
    } return array;
}
int main()
{
    int a[9], b[9];
    srand(time(0));
    populate(b);
    populate(a);
    sort(a,ARRAY_SIZE);
    sort(b,ARRAY_SIZE);
    dedupe(a);
    dedupe(b);
    sort(a,ARRAY_SIZE);
    sort(b,ARRAY_SIZE);
    for(int i=0; i<10; i++)
    {   cout << "a[" << i << "] = " << a[i] << "\t\t" << "b[" << i << "] = " << b[i] << endl; }
    return 0;
}

Nothing suggested so far has solved the problem. Does anyone know of a solution?

Answer 1

You're not returning from inside the for loop... so it should run exactly ARRAY_SIZE times each time.

Answer 2

The problem that you want to solve and the algorithm that you provided do not really match. You do not really want to remove the duplicates, but rather guarantee that all the elements in the array are different, the difference being that by removing duplicates the number of elements in the array would be less than the size of the array, but you want a full array.

I don't know what the perfect solution would be (algorithmically), but one simple answer would be creating an array of all the values in the valid range (since the range is small), shuffling it and then picking up the first N elements. Think of this as using cards to pick the values.

 const int array_size = 9;
 void create_array( int (&array)[array_size] ) {
    const int max_value = 51;
    int range[max_value];
    for ( int i = 0; i < max_value; ++i ) {
       range[i] = i;
    }
    std::random_shuffle( range, range+max_value );
    std::copy_n( range, array_size, array );
 }

This is not the most efficient approach, but it is simple, and with a small number of elements there should not be any performance issues. A more complex approach would be to initialize the array with the random elements in the range, sort and remove duplicates (actually remove, which means that the array will not be full at the end) and then continue generating numbers and checking whether they are new against the previously generated numbers.

Simplest approach is just comparing with every other value which is linear time but on an array of 9 elements linear time is small enough not to matter.

Answer 3

you are doing it wrong at array[j] = rand(); array[j] = array[j] % 51

It will always have 1 to ARRAY SIZE!!