Keep two pointers - p1 and p2
p1 points at the index just after last 0 such that there are all zero's
before it.
p2 points at the entry just before last 2, and there are all 2's after it.
*example*- 0010201201222
p1 = 2; p2 = 9;
*Pseudo code - *
p1 = 0;
p2 = n-1;
i = 0;
while(i<n)
if(A[i]) ==0) swap(p1,i); p1++;
else if (A[i]==1) i++;
else if(A[i]==2) swap (p2,i); p2--;
On Sat, Sep 24, 2011 at 11:39 AM, Yogesh Yadav <[email protected]> wrote:
> we cant traverse the string twice...
>
> if there is an error in my logic then plz tell....
>
> my logic is:
> we have to take starting and ending indexes for '0','1','2' like below
>
> 0 1 2
> starting_index
> ending_index
>
>
> now suppose our string "102112011"
>
> so we start from the left and traverse the whole string
>
> first character ='1'
>
> 0 1 2
> starting_index 0
> ending_index 0
>
> next character = '0'
>
> 0 1 2
> starting_index 1 0
> ending_index 1 0
>
> ( ending_index0 > ending_index1 ) so we swap the numbers according to
> Starting_index not according to Ending_index
> So it will become
>
> 0 1 2
> starting_index 0 1
> ending_index 0 1
>
> and string will become "01"
>
> next character '2'
>
> 0 1 2
> starting_index 0 1 2
> ending_index 0 1 2
>
> (ending_index0<ending_index1<ending_index2) so ending indexes in
> increasing order...so no need to swap
>
> so string is now "012"
>
> next character '1'
>
>
> 0 1 2
> starting_index 0 1 2
> ending_index 0 3 2
>
> (ending_index1>ending_index2) so we swap the current 1 with starting index
> of 2
> so string will become "0112"
>
> 0 1 2
> starting_index 0 1 3
> ending_index 0 2 3
>
> next character '1'
>
> 0 1 2
> starting_index 0 1 3
> ending_index 0 4 3
>
> (ending_index1>ending_index2) so we swap the current 1 with starting index
> of 2
>
> so string will become "01112"
>
> 0 1 2
> starting_index 0 1 4
> ending_index 0 3 4
>
> next character '2'
>
> 0 1 2
> starting_index 0 1 4
> ending_index 0 3 5
>
> (ending_index0<ending_index1<ending_index2) so no swap
>
> so string will become "011122"
>
> next character '0'
>
>
> 0 1 2
> starting_index 0 1 4
> ending_index 6 3 5
>
>
> (ending_index0>ending_index1>ending_index2) so we swap the current 0 with
> staring index of 2 first and then with starting index of 1
> so string will become "0011122"
>
> 0 1 2
> starting_index 0 2 5
> ending_index 1 4 6
>
>
> and so on.... i hope its much explained...
>
>
> ....
>
>
>
> On Sat, Sep 24, 2011 at 10:30 AM, Dheeraj Sharma <
> [email protected]> wrote:
>
>> char str[100],t;
>> scanf("%s",str);
>> char ch='0';
>> int i=0,j=0;
>> while(j<strlen(str))
>> {
>> if(str[j]==ch)
>> {
>> SWAP(str[i],str[j],t);
>> i++;
>> }
>> j++;
>> }
>> ch='1';
>> j=i;
>> while(j<strlen(str))
>> {
>> if(str[j]==ch)
>> {
>> SWAP(str[i],str[j],t);
>> i++;
>> }
>> j++;
>> }
>> printf("%s\n",str);
>>
>>
>> On Sat, Sep 24, 2011 at 9:55 AM, Anup Ghatage <[email protected]> wrote:
>>
>>> Is this like the segregating all the 1's to the right and the 0's to the
>>> left
>>> or am i missing something?
>>>
>>>
>>> On Sat, Sep 24, 2011 at 9:39 AM, VIHARRI <[email protected]> wrote:
>>>
>>>> You are given a string (consisting of 0's, 1's or 2's) where 0
>>>> represents a blue ball, 1 a
>>>> red ball, and 2 a black ball. Using only swap operations (counting
>>>> sort not allowed)
>>>> rearrange the string such that all blue balls are together on one
>>>> side, followed by all red
>>>> balls, and then all black balls. You can iterate through the string
>>>> only once.
>>>> Eg 102112011 should produce 001111122?
>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>>
>>>
>>>
>>> --
>>> Anup Ghatage
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> *Dheeraj Sharma*
>> Comp Engg.
>> NIT Kurukshetra
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Nitin Garg
"Personality can open doors, but only Character can keep them open"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
