CODEWITHSUNDEEP
c++arraysalgorithm
Evaldas B
Evaldas B

Reputation: 2594

Algorithm, that removes duplicates from array doesn't work

I have an char array, that has some duplicate values:

A B C D E F E A

And this is my algorithm to remove the duplicate values:

char array[20] = {'A', 'B', 'C', 'D', 'E', 'F', 'E', 'A'};
int length = 8;

    for (int i = 0; i < length; i++)
    {
        for (int j = i + 1; j < length - 1; j++)
        {
            if (array[i] == array[j])
            {
                array[j] = array[j + 1];
                length--;
            }
        }
    }

EXPECTED OUTPUT: A B C D E F
OUTPUT: A B C D E F A

I have tried to run this algorithm on papers, it seems okay when I do this in writing, however it doesn't work in my application.

Upvotes: 1

Views: 152

Answers (5)

SilverS
SilverS

Reputation: 76

You should add another for loop inside the if statement check the code below:

char array[20] = {'A', 'B', 'C', 'D', 'E', 'F', 'E', 'A'};

int length = 8;

for(int i = 0; i <= length; i++){

        for(int j = i+1; j <= length; j++){

                if(array[j] == array[i]){

                            for(int x = j+1; x <=length; x++){

                                    array[j]=array[x];

                                    }
                            length--;
                            }

                }

        }

for(int z = 0; z <= length; z++){
      cout << array[z] << " ";
      }
      cout << endl;

Upvotes: 2

davidhigh
davidhigh

Reputation: 15528

Though I know it doesn't directly solve the question, here is the better-code alternative by which you can avoid such problems (requires C++11 for the vector initialization):

std::vector<char> in{'A', 'B', 'C', 'D', 'E', 'F', 'E', 'A'};
std::vector<char> out;

std::sort (in.begin(),in.end());

std::unique_copy(in.begin(), in.end(), std::back_inserter(out));

If you do not need a copy, you can also use std::unique instead of std::unique_copy.

Upvotes: 1

sereneL
sereneL

Reputation: 15

It only works from i=0 through 3.

When i=4, array[4] = 'E', array[j] = 'F', it passes. j++ When i=4, array[4] = 'E', array[j] = 'E', array[j] is set to array[j+1], which is 'A'.

Shifting works fine but the loop for i may be the whole length of the array instead of changed length, since it stops when i=5.

Upvotes: 0

Mark Taylor
Mark Taylor

Reputation: 1851

j < length allows [j + 1] to go beyond length

As elements are moved, length is no longer the length of valid data. counter might be, but you don't show the code for how it is initialized.

Question edited to use length-- instead of counter-- but the error is in advancing j all the way to the end in the inner loop which contains a j + 1. There is also no need to extend take i all the way to length in the outer loop since the inner loop sets jet to i + 1

Upvotes: 1

Sebastian Redl
Sebastian Redl

Reputation: 72215

You have undefined behavior.

In the first iteration of the outer loop (i = 0) and the last iteration of the inner loop (j = 7, where length = 8), array[i] == array[j] is true because both are 'A'. But then you access array[j+1], which is outside the bounds.

Then, when i = 4 and j = 6, you copy the value at 7 (which is now overwritten with garbage, but apparently happens to be 'A' in your case) to index 6, giving the wrong result you see.

You need to make the copying of the element conditional on j < (length - 1) to avoid the UB. Then you should get the right result in this instance at least.

Upvotes: 2

Related Questions