array partition

[sdsu619]

hey i am trying to write a function
--------------------------------------------------------------------------------
int partition(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 none. For example,

string folks[6] = { "obiwan", "minnie", "han", "simba", "jabba", "ariel" };
int x = partition(folks, 6, "mickey"); // returns 3
// folks must now be
// "han" "ariel" "jabba" "simba" "obiwan" "minnie"
// or "jabba" "han" "ariel" "obiwan" "minnie" "simba"
// or one of several other orderings.
// All elements < "mickey" (i.e., "ariel", "jabba", and "han")
// come before all others
// All elements > "mickey" (i.e., "simba", "minnie", and "obiwan")
// come after all others
string folks2[4] = { "han", "simba", "jabba", "ariel" };
int y = partition(folks2, 4, "han"); // returns 1
// sibs must now be either
// "ariel" "han" "simba" "jabba"
// or "ariel" "han" "jabba" "simba"
// All elements < "han" (i.e., "ariel") come before all others.
// All elements > "han" (i.e., "jabba" and "simba") come after all
// others.

----------------------------------------------------------------------------
and have written one that i feel should be working, but when i test it all the elements are the same as the original.
For example if i call partition(folks, 6, "mickey"); and cout elements 0-5, it is the same order as "obiwan", "minnie", "han", "simba", "jabba", "ariel". It does return the correct number

int partition(string a[], int n, string separator)
{
	int apos=0;			
	int posofseparator=0;	// end of while = 3
	while(apos<n)
	{
		if(separator > a[apos])
			posofseparator++;
		apos++;
	}
	apos = 0;					//6
	int posifgreater = 0;		//3	
	int posiflesser = 0;		//3
	while(apos<n)
	{
		if(a[apos]>separator)
		{
			a[posofseparator+posifgreater]==a[apos];
			posifgreater++;
			apos++;
		}
		if(a[apos]<separator)
		{
			a[posofseparator-1-posiflesser]==a[apos];
			posiflesser++;
			apos++;
		}
	}
	cerr <<a[0] << endl;
	cerr <<a[1] << endl;
	cerr << a[2] << endl;
	cerr << a[3] << endl;
	cerr << a[4] << endl;
	cerr << a[5] << endl;
	return posofseparator;
}

does anyone know whats wrong

[fg109]

You are using double equal signs when you should be using single equal signs.

At any rate, your algorithm is wrong. For example, if your array was
string a[] = {"Delta", "Alpha", "Beta", "Charlie"};
Then calling your function like this:
int x = partition(a, 4, "Beta");
would result in your array becoming:
{"Delta", "Alpha", "Delta", "Charlie"}

[sdsu619]

Ah you are right thanks for the tip. Would it be plausible to create another array to store the values temporarily before transferring them back to the desired array?

[fg109]

Yes, you can create a new array to store the values first. You can try something like this:

int partition(string a[], int size, string separator)
{
    string *tmparr1, *tmparr2;
    int i1, i2, pos;

    for (pos = 0; pos < size; pos++)
    {
        if (a[pos] > separator)
            break;
    }

    i1 = pos;
    tmparr1 = new string[i1];
    i2 = size - pos;
    tmparr2 = new string[i2];

    //rest of your code here

    delete tmparr1;
    delete tmparr2;

    return pos;
}