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.
