@Minotauras:
There are some problems in you swap(x,y)
in your example : for reverse(3) you have considered 0 based indexing
and for reverse(2) 1 based index !!
see:
Original array : 1 8 3 4 5 and we want to swap(2,3) // swap 3 and 4.
Means, 0 BASED INDEX
reverse(3): 4 3 8 1 5
reverse(2): 8 3 4 1 5 <--------
reverse(3): 1 4 3 8 5
AND
If you meant swap(x,y) => rev(y) ; rev(1) ; rev(y) then, your
swap(x,y) can't be used in ALL sorting algos.
For example,
Original array : 1 4 3 2
and we want to swap(1,3) // because we want 1 2 3 4
so....
rev(3) - 2 3 4 1
rev(1) - 3 2 4 1
rev(3) - 1 4 2 3
So we have a restriction of swapping only two consecutive numbers....
so...In swap(x,y) x is not needed because {x<y && x+1=y}
On Sep 17, 12:17 am, Minotauraus <anike...@gmail.com> wrote:
> write a function swap(x, y)
> which does:
> reverse(y)
> reverse(1)
> reverse(y)
>
> so 1 8 3 4 5, swap (2, 3) // swap 3 and 4
> reverse(3) gives: 4 3 8 1 5
> reverse(2) : 3 4 8 1 5
> reverse(3): 1 8 3 4 5 //thus we have swapped 3, 4 using the reverse(x)
> function.
>
> Use any sorting algorithm and you'll need 3k * n(log n)
> assuming reverse(x) takes O(k)
>
> I guess there is a way to optimize the number of reverse(x) calls
>
> On Sep 16, 8:41 am, Srinivas <lavudyasrinivas0...@gmail.com> wrote:
>
>
>
> > You have been given a function rev(x) which works as follows:
> > It reverses a[0] to a[x] elements of a.
> > e.g. Given array is
> > a : 1 8 3 4 5
> > rev(3) will convert the array to
> > a : 4 3 8 1 5
> > Use this function only (and comparison, of course) to sort given array
> > 'a'. The only criterion is
> > that the number of times this function is called should be minimum.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
