sort array of strings with a function

Question

I am intenting sort an array of strings with this code:

void sort(string scadena[]){
    string temp;

    //here i am intenting sort the elements. it works fine

    for(int i=0;i<m;i++){
        for(int j=i+1;j<m;j++){
            if(scadena[i]>scadena[j]){
                temp=scadena[i];
                scadena[i]=scadena[j];
                scadena[j]=temp;    
            }           
        }
    }

    // Here i am intenting remove the repeated elements, but it not works fine.
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            if(scadena[i]==scadena[j] && j!=i){
                for(int k=j;k <m; k++){
                    scadena[k]=scadena[k+1];
                }
                m--;
            }
        }
    }   

    //Because when i do the cout, the output has repeated elements. it not works
    for(int i=0;i<m;i++){
        cout<<i<<") "<<scadena[i]<<endl;
    }   
}

The output has repeated elements, but i do not why.

The full code has a function that do the permutation of strings.

I do not what happen.

Any reason not to use [`std::sort`](http://en.cppreference.com/w/cpp/algorithm/sort)? — juanchopanza, Jul 01 '13 at 20:18
@juanchopanza its homework so he cant use it. See here: http://stackoverflow.com/questions/17396222/how-to-generate-all-permutations-of-an-array-in-sorted-order — Borgleader, Jul 01 '13 at 20:26

score 3 · Answer 1 · answered Jul 01 '13 at 20:26

Edit I've just seen this is for homework. Anyway, once you are done with that, here is an idiomatic C++ way to sort a vector of strings, and remove duplicates:

#include <algorithm> // for sort and unique
#include <vector>
#include <string>

....

std::vector<std::string> strings = ....;
std::sort(std::begin(strings), std::end(strings));
auto it = std::unique(std::begin(strings), std::end(strings));
strings.erase(it, std::end(strings);

score 3 · Accepted Answer · answered Jul 01 '13 at 20:27

The main problem is that when you delete an element from the array, you shouldn't be incrementing the j index, because the string at the current index will have changed, so you need to check it again.

You can fix that by decrementing j at the same time as you decrement m.

Also, it looks like you are overrunning the end of the array in the delete loop.

for(int k=j;k <m; k++){
    scadena[k]=scadena[k+1];
}

Note that when k reaches the last iteration (i.e. k = m-1), you're going to be copy from a position m which is past the end.

The updated loop with both fixes should look like this:

for(int i=0;i<m;i++){
    for(int j=0;j<m;j++){
        if(scadena[i]==scadena[j] && j!=i){
            for(int k=j;k+1 <m; k++){
                scadena[k]=scadena[k+1];
            }
            m--;
            j--;
        }
    }
}

score 1 · Answer 3 · answered Jul 02 '13 at 00:37

If your sorting works correctly, then you dont need to loop over both i and j to compare strings. You only need to loop over one index and compare with the next string. Then you delete the next string if they are equal, and only increment the index if they are different.

Here are some pseudo code:

int i=0;
while(i+1<m)
  {
    if(scadena[i]==scadena[i+1])
      {
         // Delete scadena[i+1]
         .......
         m--;
      }
    else
      i++;
  }

alexbuisson · Answer 4 · 2013-07-01T20:40:06.400

0

You modify your n loop upper limit in the loop body it may be the reason of your problem,

so remove the line

 m--;

and track the remaining number of string in another variable It's a common good practice when you write a loop of keeping the stop condition stable.

edited Jul 01 '13 at 20:40

answered Jul 01 '13 at 20:25

alexbuisson

7,699
3
31
44

i do not understand your idea – Code Geas Coder Jul 01 '13 at 20:33

score 0 · Answer 5 · answered Jul 01 '13 at 20:28

0

This should work!

for(int i=0;i<m;i++){
    for(int j=0;j<m;j++){
        if(scadena[i]==scadena[j] && j!=i){
            for(int k=j;k <(m-1); k++){
                scadena[k]=scadena[k+1];
            }
        }
    }
}

answered Jul 01 '13 at 20:28

dnawab

113
1
2
8

sort array of strings with a function

5 Answers5