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 <medu...@gmail.com> 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 < > dheerajsharma1...@gmail.com> 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 <ghat...@gmail.com> 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 <viharri....@gmail.com> 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 algogeeks@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com. >>>> 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 algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.