array partition

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
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"}
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?
Yes, you can create a new array to store the values first. You can try something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}
Last edited on
Topic archived. No new replies allowed.