Algorithm, that removes duplicates from array doesn't work

Question

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.

Sorry I haven't rewritten it when I was posting here. It should be length instead of counter. — Evaldas B
– Evaldas B, Commented Nov 4, 2014 at 13:40
Your "duplicate removal" step reliably creates a new duplicate. Instead of a[j] == a[i] you now have a[j] == a[j+1]. Always — Ben Voigt
– Ben Voigt, Commented Nov 4, 2014 at 13:44
Learn about single stepping in a debugger, perhaps. Beats "tried to run on paper" every time. — Ben Voigt
– Ben Voigt, Commented Nov 4, 2014 at 13:46

SilverS · Accepted Answer · 2014-11-04 16:06:58Z

2

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;

answered Nov 4, 2014 at 16:06

SilverS

763 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sebastian Redl · Accepted Answer · 2014-11-04 13:44:04Z

2

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.

answered Nov 4, 2014 at 13:44

Sebastian Redl

73.9k8 gold badges137 silver badges177 bronze badges

3 Comments

Ben Voigt Over a year ago

Question edit reveals: There is extra space after the real data, containing NULs.

Evaldas B Over a year ago

I have changed j < length to j < (length - 1), the output is A B C D E F A

Sebastian Redl Over a year ago

@EvaldasB Well, that's wrong too. You need to check that last element, but you shouldn't copy from beyond it.

Mark Taylor · Accepted Answer · 2014-11-04 13:48:07Z

1

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

edited Nov 4, 2014 at 13:48

answered Nov 4, 2014 at 13:41

Mark Taylor

1,85114 silver badges17 bronze badges

1 Comment

Evaldas B Over a year ago

So in first loop is set i < length - 1, so that last element wouldn't be checked and I can check the last element in other array. However the problem still persists.

davidhigh · Accepted Answer · 2014-11-04 14:38:38Z

1

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.

edited Nov 4, 2014 at 14:38

answered Nov 4, 2014 at 14:04

davidhigh

15.7k2 gold badges49 silver badges82 bronze badges

3 Comments

Anton Savin Over a year ago

std::unique_copy removes only consecutive duplicates

davidhigh Over a year ago

THanks for the comment. So one has to do a sort in advance.

Anton Savin Over a year ago

You have to sort in, not out :)

sereneL · Accepted Answer · 2014-11-04 14:28:17Z

0

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.

answered Nov 4, 2014 at 14:28

sereneL

254 bronze badges

Collectives™ on Stack Overflow

Algorithm, that removes duplicates from array doesn't work

5 Answers 5

Comments

3 Comments

1 Comment

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

3 Comments

1 Comment

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related