#include<stdio.h>
main(){ //{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
int i,a[]={0,1,1,2,2,3,3,4,4,5,5, 6, 6, 7, 7, 8, 8};
int count,temp,value_of_i,m=0;
for(i=0;i<16;i++)
printf("%d ",i);
printf("\n");
for(i=0;i<16;i++)
printf("%d ",a[i]);
i=2;
value_of_i=1;
printf("\n");
for(count=0;count<13;count++)
{
if(i%2==0)
{
i=7+i/2;
temp=a[i];
a[i]=value_of_i;
value_of_i=temp;
printf("(%d %d) \n ",i,value_of_i);
}
else
{
i=(1+i)/2; ;
temp=a[i];
a[i]=value_of_i;
value_of_i=temp;
printf("(%d %d)\n", i,value_of_i);
}
for(m=1;m<17;m++)
printf("%d ",a[m]);
}
printf("hi");
}
On Nov 16, 7:29 pm, "Vikram Venkatesan" <[EMAIL PROTECTED]>
wrote:
> Hi Ksitami,
> In the first algorithm, what if the CYLCE OF REPLACEMENTS sorts the
> whole array(I mean, all the elements are visited during the 1st iteration
> itself, thus creating a COMPLETE CYCLE of the array, putting it in the right
> order), and the array gets to the FINAL position (i.e. a1a2...b1b2...)
> before 'i' could reach n/2 ?.
>
> In that case, won't the REPEAT ..UNTIL block be MODIFYING ELEMENTS THAT HAVE
> ALREADY BEEN MOVED TO THEIR CORRECT POSITIONS...
>
> In general, how can we be sure that 'i' doesn't pick up elements that are
> already sorted? (during successive iterations of WHILE, as a result of i +=
> 2)
>
> Pls correct me if i am wrong...
>
> Thanks,
> Vikram
>
> On 11/16/06, Ksitami <[EMAIL PROTECTED]> wrote:
>
>
>
> > Idris napisał(a):
> > > How about using 1 variable o(1) Space..
>
> > > i.e Scan the array and compare the element... at a[1]=a1, a[2]=b1,
> > > a[3]=a2,......
>
> > > first check(a[i]), say b2 in array of size 8, so Its clear b2 must be
> > > placed at 8/2+2 position in an array..
>
> > "012345678" => "024681357"
> > .------------------------------------------
> > . Idris agorithm
> > . SubLinear but not deterministic
> > .
> > . n2=n div 2
> > . if odd(n) then n2+=1 //n2 first odd
> > . i=1
> > . while i<n2
> > . firsti=i
> > . x=t[i]
> > . if odd(i)
> > . then i=i div 2 + n2
> > . else i=i div 2
> > . repeat
> > . b=t[i]; t[i]=x; x=b
> > . if odd(i)
> > . then i:=i div 2 + n2
> > . else i:=i div 2
> > . until firsti=i
> > . t[i]=x; lz+=1
> > . i+= 2 * MagicDice // here is magic ;-)
> > .------------------------------------------
>
> > But,
> > .------------------------------------------
> > . // OddSort
> > . n2= n div 2
> > . if odd(n) n2++ //extra
> > . for j=1 to n2-1
> > . k= j
> > . if j>1
> > . repeat
> > . k= (k*2) mod (2*n2 - 1);
> > . until k<=j
> > . if k=j
> > . store=t[j]
> > . y=j
> > . repeat
> > . k=y
> > . y= (2*k) mod (2*n2 - 1)
> > . t[k]= t[y]
> > . until y=j
> > . t[k]=store
> > . from:
> > . "A Handbook of Time-Series Analysis,
> > . Signal Processing and Dynamics"
> > . by D. S. G. Pollock
> > .------------------------------------------
--~--~---------~--~----~------------~-------~--~----~
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-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
