@guarav true.... @others no point in sending the code.... describe your logic... anyway link provided by guarav is suffice to solve the problem
On Sat, Sep 24, 2011 at 5:26 PM, Gaurav Aggarwal <[email protected]>wrote: > Classic problem http://en.wikipedia.org/wiki/Dutch_national_flag_problem > > > > On Sat, Sep 24, 2011 at 5:15 PM, Ankur Garg <[email protected]> wrote: > >> void sort012(int a[],int n){ >> int i = 0, s = 0, last = n-1; >> while(i<=last){ >> if(a[i] == 0 && i!=s) >> { >> swap(a[i], a[s]); >> s++; >> } >> else if(a[i] == 2 && i!=last) >> { >> swap(a[i], a[last]); >> last--; >> } >> else >> i++; >> } >> } >> >> >> >> On Sat, Sep 24, 2011 at 5:13 PM, Ankit Sinha <[email protected]> wrote: >> >>> I think this will do the same: - >>> >>> #include "stdafx.h" >>> #include "stdlib.h" >>> >>> void swap(int *a, int start, int end) >>> { >>> int temp; >>> temp = *(a + start); >>> *(a + start) = *(a + end); >>> *(a + end) = temp; >>> } >>> >>> int _tmain(int argc, _TCHAR* argv[]) >>> { >>> int minIndex=0, maxIndex=8; >>> int i=1; >>> int a[9] ={1,0,2,1,0,2,0,0,1}; >>> while(i<maxIndex) >>> { >>> if(a[maxIndex] == 2) >>> maxIndex--; >>> if(a[minIndex] == 0) >>> minIndex++; >>> if(a[i] > a[maxIndex]) >>> { >>> swap(a, i, maxIndex); >>> continue; >>> } >>> else if (a[i] < a[minIndex]) >>> { >>> swap(a, i, minIndex); >>> continue; >>> } >>> i++; >>> } >>> for (i =0 ; i< 9; i++) >>> printf("[%d]", a[i]); >>> system("PAUSE"); >>> return 0; >>> } >>> Please comment. >>> >>> Cheers, >>> Ankit Sinha >>> >>> On Sat, Sep 24, 2011 at 4:10 PM, malay chakrabarti <[email protected]> >>> wrote: >>> > dutch national flag problem :) >>> > >>> > On Sat, Sep 24, 2011 at 3:45 PM, Dheeraj Sharma >>> > <[email protected]> wrote: >>> >> >>> >> i think this travels only once ... correct me if am wrong >>> >> #include<stdio.h> >>> >> #include<string.h> >>> >> #define SWAP(a,b,c) (c)=(a),(a)=(b),(b)=(c) >>> >> int main() >>> >> { >>> >> int t,x; >>> >> scanf("%d",&t); >>> >> while(t--) >>> >> { >>> >> char str[100]; >>> >> scanf("%s",str); >>> >> int i=0,j=0,k=strlen(str)-1; >>> >> >>> >> while(str[i]=='0') >>> >> i++; >>> >> while(str[k]=='2') >>> >> k--; >>> >> >>> >> j=i; >>> >> while(j<=k) >>> >> { >>> >> if(str[j]=='2') >>> >> { >>> >> SWAP(str[j],str[k],x); >>> >> k--; >>> >> } >>> >> >>> >> if(str[j]=='0') >>> >> { >>> >> SWAP(str[i],str[j],x); >>> >> i++; >>> >> } >>> >> if(str[j]!='2') >>> >> j++; >>> >> } >>> >> >>> >> printf("%s\n",str); >>> >> } >>> >> return 0; >>> >> } >>> >> >>> >> >>> >> 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. >>> >> >>> >> >>> >> >>> >> -- >>> >> 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. >>> > >>> >>> -- >>> 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. >> > > > > -- > regards, > > Gaurav Aggarwal > > > -- > 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.
