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.
