Sorting dynamically allocated array

Question

for some reason I cannot spot the error that I causing me to fail my test cases. im writing a function that is supposed to do the following.

int separate(string a[], int n, string separator);
Rearrange the elements of the array so that all the elements whose value is   < separator come before all the other elements, and all the elements whose value  is > separator come after all the other elements. Return the position of the first element that, after the rearrangement, is not < separator, or n if there are no such elements. For example,
string cand[6] = { "donald", "jill", "hillary", "tim", "evan", "bill" };
int x = separate(cand, 6, "gary");  //  returns 3
// cand must now be
//      "donald"  "evan"  "bill"  "jill"  "tim"  "hillary"
// or   "evan"  "bill"  "donald"  "hillary"  "jill"  "tim"
// or one of several other orderings.
// All elements < "gary" (i.e., "evan", "bill", and "donald")
//   come before all others
// All elements > "gary" (i.e., "tim", "jill", and "hillary")
//   come after all others

My approach is to use dynamically allocated arrays to store the values that are > than seperator.

int split(string a[], int n, string separator){

int lessThanSep = 0;
int greatThanSep = 0;

for(int i = 0; i < n; i++){
    if(a[i] < separator){ //adding the number that are less Than Seperator
        lessThanSep++;
    }
   else if(a[i] > separator){ //adding the number that are Greater Than     Seperator
       greatThanSep++;
    }
}
int finalSize = greatThanSep + lessThanSep;

string *lessThan = new string[lessThanSep]();
string *greatThan = new string[greatThanSep]();

string *final = new string[finalSize]();


for(int i = 0; i < n; i++){
    if(a[i] < separator){ //adding the number that are less Than Seperator
        lessThan[i] = a[i];
    }
    else if(a[i] > separator){ //adding the number that are Greater Than Seperator
        greatThan[i] = a[i];
    }
}
for(int i = 0; i < lessThanSep; i++)
    final[i] = lessThan[i];

for(int i = lessThanSep; i < greatThanSep; i++)
    final[i] = greatThan[i];

for(int i = 0; i < finalSize; i++){
    if( final[i] > separator)
        return i;
}

return n;
}

HERE are my test cases...Im faling the first one.

  void testSplit()
   {
  string stuffAns[] = {"animals", "bagels", "camels", "dolphins", "earwax"};
  string stuff1[] = {"animals", "bagels", "camels", "dolphins", "earwax"};
  string stuff2[] = {"animals", "bagels", "camels", "dolphins", "earwax"};
  string stuff3[] = {"animals", "bagels", "camels", "dolphins", "earwax"};
  string stuff4[] = {"animals", "bagels", "camels", "dolphins", "earwax"};
  string stuff5[] = {"animals", "bagels", "camels", "dolphins", "earwax"};

assert(split(stuff1, 5, "camels")==2); //test if a sorted array (target in    the middle) returns the right index
assert(split(stuff2, 5, "animals")==0); //test if a sorted array (target in the front) returns the right index
assert(split(stuff3, 5, "az")==1); //test if a sorted array (target nonexistent but at index 1) returns the right index
assert(split(stuff4, 5, "ear")==4); //test if a sorted array (target one before the end) returns the right index
assert(split(stuff5, 5, "ez")==5); //test if n is returned if all strings are less than "ez"

for(int k=0; k<5; k++) //check that no arrays are changed, since they were already sorted
{
    assert(stuff1[k]==stuffAns[k]);
    assert(stuff2[k]==stuffAns[k]);
    assert(stuff3[k]==stuffAns[k]);
    assert(stuff4[k]==stuffAns[k]);
    assert(stuff5[k]==stuffAns[k]);
}


string stuffAns6[] = {"c", "b", "a", "q", "d", "z"};
string stuffAns7[] = {"c", "d", "q", "b", "a", "z"};
string stuff6[] = {"c", "q", "d", "b", "a", "z"};
string stuff7[] = {"c", "q", "d", "b", "a", "z"};

assert(split(stuff6, 6, "ce")==3); //see if correct position is returned in an unsorted array

for(int k=0; k<5; k++)
{
    assert(stuff6[k]==stuffAns6[k]); //see if the array is sorted as expected
}

assert(split(stuff7, 3, "darnit")==2); //see if correct position is returned in an unsorted array

for(int k=0; k<5; k++)
{
    assert(stuff7[k]==stuffAns7[k]); //see if the array is sorted as expected
}

cerr << "All tests for split() succeeded!" << endl;
}

Any help would be much appreciated.

Answer 1

Unless you must use arrays, may I suggest using std::list? Your split function would look much cleaner and simpler using this library:

int split(list<string> &L, int n, string S) {
    list<string> temp;
    int m = 0;
    for (list<string>::iterator i = L.begin(); i != L.end(); i++) {
        if (*i < S) temp.push_front(*i);
        else {
            temp.push_back(*i);
            m++;
        }
    }
    L.swap(temp);
    return m ? L.size() - m : n;
}

Side note: you didn't have an exception for equal strings so I just put them in the back with the higher-valued strings.