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.
